BOJ 1149 RGB거리 python3

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

1149번: RGB거리

 

 

코드

from sys import stdin
input = stdin.readline

R, G, B = 0, 1, 2
N = int(input())
houses = [[-1, -1, -1] for _ in range(N)]

# 각 집의 색깔 별 가격 입력
for i in range(N):
    houses[i] = list(map(int, input().split(" ")))

dp = [[-1, -1, -1] for _ in range(N)]
dp[0] = houses[0]

# 각 집에 대하여 dp 돌리기
for i in range(1, N):
    # i번째 집이 R일 경우 최소 cost
    dp[i][R] = houses[i][R] + min(dp[i-1][G], dp[i-1][B])
    # i번째 집이 G일 경우
    dp[i][G] = houses[i][G] + min(dp[i-1][R], dp[i-1][B])
    # i번째 집이 B일 경우
    dp[i][B] = houses[i][B] + min(dp[i-1][R], dp[i-1][G])

# 최솟값 출력
print(min(dp[N-1]))

 

 

해설

dp를 활용해서 푸는 문제이다.

 

문제의 조건은 다음과 같다.

• f(1) != f(2)
• f(N) != f(N-1)
• f(i) != f(i-1)
• f(i) != f(i+1)

여러 개의 조건이 있는 듯 해보이지만, 자세히 보면 결국 조건은 f(i) != f(i-1) and f(i) != f(i+1) 뿐이다.

 

그리드를 그리기 위해 축과 셀에 들어갈 값들을 생각해보자.

• x축 : 색 (R, G, B)
• y축 : 각각의 집 번호
• cell : i번째 집이 X색일 때 최소 비용

그림 1. 그리드 

 

0번째 집에서의 최소 비용은 houses[0]과 같으므로 0행은 다음과 같이 채울 수 있다.

 

그림 2. 0행을 채운 그리드

 

1행부터는 다음과 같이 채울 수 있다.

1. 1번째 집이 Red라면, 0번째 집은 Green 혹은 Blue 이다.
2. 1번째 집이 Green이라면, 0번째 집은 Red 혹은 Blue 이다.
3. 1번째 집이 Blue라면, 0번째 집은 Red 혹은 Greed 이다.

따라서 1번째 집이 Red 라면, 0번째 집의 Green과 Blue의 비용을 비교하여 최솟값을 선택하면 된다.

즉, dp[i][R] = houses[i][R] + min(dp[i-1][G], dp[i-1][B]) 이다.

 

그림 3. 1행을 채운 그리드

그 다음 행들도 동일하게 채워주면 된다.

 

그림 4. 모든 행을 채운 그리드

모든 행이 채워졌을 때, 마지막 행에서의 최솟값인 13+83=96 을 출력하게 된다.