[백준/실버1] 1149번 RGB거리 | DP | 파이썬 Python

문제

https://www.acmicpc.net/problem/1149

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보다 작거나 같은 자연수이다.

 

출력

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

 

예제

 

다른 사람의 풀이

N = int(input())
dp = [[0] * 3 for _ in range(N)]

for i in range(N):
    house = list(map(int, input().split()))
    dp[i] = house

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

print(min(dp[N-1]))

• 첫 번째 집에서부터 시작해서 각각의 색을 선택했을 때의 최소 비용을 저장해 나가면서, 마지막 집의 최소 비용을 구한다.
• 현재 집까지 칠했을 때의 최소 비용을 구하려면, 이전까지의 최소 비용에 현재 비용을 더하면 된다.
• 집을 칠하는 비용을 2차원 리스트 형태로 저장하는데, `dp[i][0]`은 `i`번 집을 빨간 색으로 칠했을 때 지금까지의 최소 비용을 담고 있다.
  • 만약 `i`번째 집을 빨간색으로 칠한다면 `dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + 현재 집을 빨간색으로 칠하는 비용`으로 계산한다.

 

회고

• 비록 이 문제도 내 힘으로 풀진 못했지만 이제 어느 정도 DP 문제의 패턴이 보이는 거 같다.
• 특히 최소값을 구하는 경우에는 `이전까지의 최소값 + 현재 값을 더하는 방법`으로 접근하면 될 거 같다.
  • 만약에 선택지가 A, B라면 현재의 최소값을 구하는 방법은 `이전 최소값 + 현재 A의 값` 또는 `이전 최소값 + 현재 B의 값` 두 가지 경우가 존재할 수 있다.
• 특히 DP 테이블을 어떤 형태로 구현해야 할까에서 막히는 경우가 많은데 기본적으로는 `N`의 길이를 가지는 리스트를 만들고, 2차원 리스트로 확장할 수도 있다는 점을 기억하자!