태야

<내 코드>

N = int(input())

times = [list(map(int, input().split())) for _ in range(N)]
times.sort(key=lambda x: (x[1], x[0])) # 끝 시간으로 정렬 후, 시작 시간으로 정렬

cnt = 1
end_time = times[0][1]
for i in range(1, N):
    if times[i][0] >= end_time: # 앞 요소의 끝 시간보다 현재 요소의 시작시간이 크거나 같을 때
        cnt += 1
        end_time = times[i][1]

print(cnt)

문제에서 제약조건이 다음과 같이 주어졌다.

- 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

- 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

최대한 많은 회의를 잡기 위해서는 끝나는 시간이 짧아야 한다. 회의가 빨리 끝나야 다음 회의를 시작할 수 있다. 

그래서 우선 끝나는 시간으로 정렬한다. 여기서 중요한 것이 시작 시간과 끝나는 시간이 같은 케이스다.

예를 들어 (2,2) 와 (1,2) 있을 때 끝나는 시간으로 정렬을 한다면 (2,2)가 먼저 정렬되고 (1,2)가 무시된다. 그래서 시작과 끝 시간이 같은 경우는 시작 시간 기준으로 다시 정렬을 해줘야 한다.

<내 코드>

n = input().split('-')
result = 0

for i in n[0].split('+'):
    result += int(i)

for j in n[1:]:
    for k in j.split('+'):
        result -= int(k)

print(result)

적절한 괄호를 쳐서 최솟값을 만드는 문제다. 최솟값을 만들려면 -의 값이 커야 하기에 - 사이에 +로 연결된 값들을 다 더한 후 마지막 빼주면 최솟값을 만들 수 있다. 어떤 점에서 그리디 문제인지는 감이 오지 않는 문제다...

<내 코드>

n = int(input())
tri = [list(map(int, input().split())) for _ in range(n)]
k = 2
for i in range(1, n):
    for j in range(len(tri[i])):
        if j == 0:  # 가장 왼쪽값일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][j] + tri[i][j]
        elif j == len(tri[i])-1:    # 가장 오른쪽일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][-1] + tri[i][j]
        else:  # 양 끝값이 아닌, 중간일 경우, 대각선 왼쪽과 오른쪽 중 큰 값과 더함
            tri[i][j] = max(tri[i-1][j-1], tri[i-1][j]) + tri[i][j]
    k += 1
print(max(tri[n-1]))

규칙을 찾아서 재귀 형태의 점화식을 찾아내는 것이 중요했다. 삼각형의 가장 왼쪽과 오른쪽 값은 위의 값과 바로 더해주면 되고, 중간의 값들은 대각선 왼쪽과 오른쪽의 값 중 최댓값과 더해줬다. 

<내 코드>

n = int(input())
costs = [0 for _ in range(n+1)]
for i in range(1, n+1):
    costs[i] = list(map(int, input().split()))

for i in range(2, n+1):
    costs[i][0] = costs[i][0] + min(costs[i-1][1], costs[i-1][2])
    costs[i][1] = costs[i][1] + min(costs[i-1][0], costs[i-1][2])
    costs[i][2] = costs[i][2] + min(costs[i-1][0], costs[i-1][1])
   
print(min(costs[n][0], costs[n][1], costs[n][2]))

처음에 생각했을 때는 맨 처음 요소에서 최솟값을 구하면 최소가 되는 줄 알았는데, 그게 아니고 어떤 값을 선택했을 때 최소가 될지는 다 따져줘야 하는 문제였다. 다른 사람의 풀이를 참고하기 전까지는 쓸데없이 어렵게 풀고 헤맸다...

1. 첫 요소는 고정이므로 인덱스를 2번째부터 돌리면 된다. 

2. 현재 인덱스 요소의 값과 앞 요소에서 같은 색을 제외한 2가지 중에 최소를 더해준다.

3. 같은 방식으로 마지막까지 3가지 색에 대해 계산을 한다.

4. 마지막 요소의 3가지 값 중 최솟값을 선택하면 최소 비용값을 구할 수 있다.