문제
[ 해결순서 ]
- 처음엔 첫 줄의 최소 값을 구하고 다음 줄에는 그 줄의 색깔을 제외한 색깔 중 최소 값을 구하려 했다.
- 그러면 전체에서의 최소 값을 구하지 못함.
- 결국 전체 경우의 수를 구해야 함
- 해당 값을 구하려면 현재의 색깔을 제외한 색깔의 행과, 직전의 열을 값들을 비교해서 작은 값에 + 현재의 비용을 더함. (비용을 더하지 않는 실수를 함)
- 마지막 줄의 색깔 중 가장 작은 값이 정답
점화식
dp[i][red]=Math.min(dp[i-1][blue],dp[i-1][green])+cost[i][red]
//빨간 색 이라면, 그 전줄의 빨간 색이 아닌 파랑, 초록 중 작은 값 + 해당 값의 가격
✏️한줄평
DP 문제를 더 자주 풀어 익숙하게 해야겠다.
코드
'알고리즘' 카테고리의 다른 글
[JAVA] 백준 11057 - 오르막 수 (0) | 2021.07.25 |
---|---|
[JAVA] 백준 7569번 - 토마토 (0) | 2021.07.25 |
[JAVA] 백준 1991번 - 트리순회 (0) | 2021.07.19 |
[JAVA] 백준 2667번 - 단지번호붙이기 (0) | 2021.07.19 |
[JAVA] 백준 1697번 - 숨바꼭질 (0) | 2021.07.19 |