매 행마다 최솟값을 골라서 기존 최솟값에 더하는 방식으로는 올바른 답을 구할 수 없습니다.
3
10 20 30 -> 10
20 10 20 -> 20
100 1 100 -> 1
이렇게 고르면 31이 나올 수 있는데 위의 소스로는 120이 나오네요
1149번 - RGB거리
매 행마다 최솟값을 골라서 기존 최솟값에 더하는 방식으로는 올바른 답을 구할 수 없습니다.
3
10 20 30 -> 10
20 10 20 -> 20
100 1 100 -> 1
이렇게 고르면 31이 나올 수 있는데 위의 소스로는 120이 나오네요
댓글을 작성하려면 로그인해야 합니다.
dlgockd54 7년 전
배열 dp의 1열(R) 2열(G) 3열(B)에 각 집의 최소 비용을 입력하고
4열에는 셋중 최소비용을 찾아서 앞의 집까지 계산된 최소비용에
현재 차례의 집 최소비용을 더하는 식으로 구현해봤습니다. (dp[i][4] = dp[i-1][4] + 현재 차례의 최소비용)
예제로 나와있는 테스트 케이스는 물론이고 제가 몇개 더 만들어서 시도했을 때는 성공했는데
틀렸습니다가 나오네요. 어디가 문제 일까요?