dlgockd54   7년 전

배열 dp의 1열(R) 2열(G) 3열(B)에 각 집의 최소 비용을 입력하고

4열에는 셋중 최소비용을 찾아서 앞의 집까지 계산된 최소비용에

현재 차례의 집 최소비용을 더하는 식으로 구현해봤습니다. (dp[i][4] = dp[i-1][4] + 현재 차례의 최소비용)

예제로 나와있는 테스트 케이스는 물론이고 제가 몇개 더 만들어서 시도했을 때는 성공했는데

틀렸습니다가 나오네요. 어디가 문제 일까요?

매 행마다 최솟값을 골라서 기존 최솟값에 더하는 방식으로는 올바른 답을 구할 수 없습니다.

3

10 20 30 -> 10

20 10 20 -> 20

100 1 100 -> 1

이렇게 고르면 31이 나올 수 있는데 위의 소스로는 120이 나오네요


dlgockd54   7년 전

답변 감사합니다!

덕분에 해결했습니다.

댓글을 작성하려면 로그인해야 합니다.