🚥 백준 1149번 : RGB거리

✏️ 문제

🔗 link : BOJ 1149번 RGB거리

💡 풀이

빨강, 초록, 파랑 색만 사용할 수 있으므로 2차원 배열을 사용해 총 3xn배열(n은 집의 수)을 만든다.

두번째 배열부터 반복문을 시작하여 첫번째 배열에서 현재 내 집 색의 비용을 제외한 나머지 색의 비용의 최솟값을 계속해서 더해준다.

26 40 83
49 60 57
13 89 99

위의 값이 입력값으로 들어온다면 d[1][0]에는 40과 83중 최솟값인 40이 두번째 배열의 첫번째 값인 49와 더해져 89값이 저장되는 것이다.

즉 점화식은 d[i][0] = min(d[i-1][1],d[i][2])+rgb[i][0] 이다.
0, 1, 2일때 모두 숫자만 바꾸고 똑같이 적용된다.

d의 첫번째 배열에 각각 원본 값의 첫번째 배열 값을 넣어주고 반복문을 돌려주면 가장 마지막 배열은 각각 최솟값이 나오게 된다. 이 중 가장 최솟값을 출력시키면 된다.

다 풀고보니 계속 틀릴만한 문제는 아닌 것 같은데 계속 틀렸던 문제다.
동적 프로그래밍 문제로 점화식만 잘 구한다면 해결이 되었을 문제..

💻 소스코드

import sys
n = int(sys.stdin.readline())
rgb = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [[0,0,0] for i in range(n)]
d[0][0] = rgb[0][0]
d[0][1] = rgb[0][1]
d[0][2] = rgb[0][2]

for i in range(1,n):
    d[i][0] = min(d[i - 1][1], d[i - 1][2]) + rgb[i][0]
    d[i][1] = min(d[i - 1][0], d[i - 1][2]) + rgb[i][1]
    d[i][2] = min(d[i - 1][0], d[i - 1][1]) + rgb[i][2]
    
print(min(d[n-1]))