백준 파이썬 1149번 RGB거리

🚀접근하기

<다이나믹 프로그래밍>

사실 처음에 문제 이해하는 게 어려웠다..

조건에서

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 

이 부분을 어떻게 구현해야 할지 처음엔 막막했는데, 결국 윗줄과 아랫줄의 색깔이 같지 않으면 되는 것이었다.

즉 R, G, B를 구분해서 R인 경우 윗 줄의 G,B 중 작은 것을 더해주고, G인 경우 윗 줄의 R,B 중 작은 것을 더해주고, B인 경우 윗 줄의 R,G 중 작은 것을 더해준 다음,

마지막에 R,G,B중 가장 작은 값을 출력해주면 된다.

🎉코드

import sys

N = int(sys.stdin.readline())
rgb_list = []

for i in range(N):
    rgb_list.append(list(map(int, input().split())))

for i in range(1, len(rgb_list)):
    rgb_list[i][0] = rgb_list[i][0] + min(rgb_list[i-1][1], rgb_list[i-1][2])
    rgb_list[i][1] = rgb_list[i][1] + min(rgb_list[i-1][0], rgb_list[i-1][2])
    rgb_list[i][2] = rgb_list[i][2] + min(rgb_list[i-1][0], rgb_list[i-1][1])

print(min(rgb_list[N-1][0], rgb_list[N-1][1], rgb_list[N-1][2]))

 

💪다짐

rgb_list[i][0] , rgb_list[i][1],  rgb_list[i][2] 처음엔 이렇게 3가지로 나누어서 차례대로 더해주면 된다는 생각을 하기까지가 시간이 오래 걸렸던 것 같다.

그래도 점점 다이나믹 프로그래밍 문제에 감이 잡혀가는 것 같다.