1149

(C++) 백준 1149번 [RGB거리]

안녕하세요 평범한 컴공생입니다! 백준 1149번 문제 [RGB거리] 알고리즘 포스팅을 시작해보겠습니다. 전형적인 DP 문제인데, 처음에 DFS로 접근을 하려했다가 시간초과가 나서 DP로 방법을 바꾸니 해결할 수 있었습니다. 1. 문제 해결 방법 구상하기 - 빨간색으로 집을 칠하면 그 다음집은 파란색 또는 초록색으로밖에 칠할 수 없다. - 초록, 파랑의 경우도 마찬가지이다. - 두 번째 집에서 예를 들어 RED로 칠한다고 하면 첫 번째 집에서의 GREEN, BLUE를 선택한 값 중 더 작은 값에 RED를 칠했을 때의 값을 더한 것이다. - 세 번째 집에서 예를 들어 RED로 칠한다고 하면 두 번째 집을 BLUE로 했을 때 소요되는 최솟값과 GREEN로 했을 때의 최솟값 중에 더 작은 값에 RED로 칠했을 ..