백준 1149번. RGB 거리 (Python / 파이썬)

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
 - 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
 - N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
 - i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

---

문제 풀이

문제에서 주어진 조건을 보면 바로 전 집의 색과 바로 다음 집의 색과

현재 집의 색이 달라야 한다는 것을 알 수 있습니다.

 

따라서 현재 집의 색을 고를 때

바로 전 집의 색과 다른 색 중 최솟값을 선택하면 됩니다.

 

DP를 이용해 이러한 조건에 따라 문제를 해결했습니다.

두번째 집부터 R,G,B 세개 동안 반복문을 수행합니다.

만약 맨 왼쪽이면 첫번째 오른쪽 위, 두번째 오른쪽 위 중 최솟값을 더해 갱신해줍니다.

만약 맨 오른쪽이면 첫번째 왼쪽 위, 두번째 왼쪽 위 중 최솟값을 더해 갱신해줍니다.

그 외의 경우에는 오른쪽 위, 왼쪽 위 중 최솟값을 더해 갱신해줍니다.

이 과정은 만약 위에서 어떤 색을 선택했을 때, 다음 집은 그 색을 제외하고 고를 경우에서

최소값을 선택하는 것과 같습니다.

 

이 과정을 모두 수행하면 list의 맨 아래줄에는 각 경우의 최솟값이 저장됩니다.

따라서 맨 아래줄에서 최솟값을 출력하면 됩니다.

---

My Code

n = int(input()) # 집의 수

dp = []
for _ in range(n):
    dp.append(list(map(int,input().split()))) # 각 집의 R,G,B 비용

for i in range(1, n): # 두번째 집부터
    for j in range(3): # R,G,B 세개 동안
        if j == 0: # 맨 왼쪽이면
            # 첫번째 오른쪽 위, 두번째 오른쪽 위 중 최솟값 선택해 더해 갱신
            dp[i][j] += min(dp[i - 1][j + 1], dp[i - 1][j + 2]) 
        elif j == 2: # 맨 오른쪽이면
            # 첫번째 왼쪽 위, 두번째 왼쪽 위 중 최솟값 선택해 더해 갱신
            dp[i][j] += min(dp[i - 1][j - 1], dp[i - 1][j - 2])
        else: # 그 외의 경우
            # 오른쪽 위, 왼쪽 위 중 최솟값 선택해 더해 갱신
            dp[i][j] += min(dp[i - 1][j - 1], dp[i - 1][j + 1])

print(min(dp[n - 1])) # 맨 아래줄에서 최솟값 출력