[문제 풀이] 백준 1149

해결 과정

처음에는 1번째 원소 부터 작은 것을 선택해서 for 문 돌면서 최솟값을 선택하도록 했는데, 테스트케이스 5번에만 답이 안나오는 것을 발견했다. 다른 풀이가 있다는 뜻이기에 고민하다 DP임을 발견 다른 풀이를 참고했다. 직관적이다. 처음 부터 작은 원소를 선택하는 것이 아니라, 1번째를 제외한 RGB 각각에 대해 최솟값을 선택하도록 하면 된다.

 

나의 풀이

N = int(input())
cost = []
for _ in range(N):
    cost.append(list(map(int, input().split())))

dp = [[0, 0, 0] for _ in range(N)]
dp[0] = cost[0]

for i in range(1, N):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]

print(min(dp[N-1]))

 

다른 풀이

 

 

IDEA

DP 아이디어.