[백준] 1149번 : RGB거리 (python 파이썬)

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

1149번: RGB거리

 

import sys

n = int(sys.stdin.readline())

dp = [[0 for i in range(n)],[0 for i in range(n)],[0 for i in range(n)]]
for i in range(n):
  
    r,g,b = map(int, sys.stdin.readline().rstrip().split(" ")) # r,b,g 입력
    if i == 0: # 처음 입력 받을 때 (dp초기 입력)
        dp[0][i] = r
        dp[1][i] = g
        dp[2][i] = b
    else:
        dp[0][i] = min(r+dp[1][i-1], r+dp[2][i-1]) # (r의 경우) 입력받은 r과 지난 b의 합과 입력받은 r과 지난 g의 합 비교하고 작은 값 집어넣기
        dp[1][i] = min(g+dp[0][i-1], g+dp[2][i-1]) # (g의 경우) 입력받은 g와 지난 r의 합과 입력받은 g와 지난 b의 합 비교하고 작은 값 집어넣기 
        dp[2][i] = min(b+dp[0][i-1], b+dp[1][i-1]) # (b의 경우) 입력받은 b와 지난 r의 합과 입력받은 b와 지난 g의 합 비교하고 작은 값 집어넣기
        

    
print(min(dp[0][-1],dp[1][-1],dp[2][-1])) # 값 출력

 

 

전형적인 dp문제 중 하나이다. 

dp의 형태는 [ [] , [] , [] ] 이며, 각각의 리스트는 r,g,b 를 의미한다. (정확하게는 r로 시작했을 경우, g로 시작했을 경우, b로 시작했을 경우)

 

 

처음 r,g,b 를 입력 받을 때에는 dp에 아무것도 없기 때문에 순서에 맞춰 dp의 처음 인덱스에 집어넣는다

 

 

다음 r,g,b를 입력 받을 때부터는

dp[i][0](r의 경우) 은 가능한 경우가 dp[i-1][1]에서 r을 더한 경우와, dp[i-1][2]에서 r을 더한 경우이다.

 

dp[i][1](g의 경우) 은 가능한 경우가 dp[i-1][0]에서 g을 더한 경우와, dp[i-1][2]에서 g을 더한 경우이다.

 

dp[i][2](b의 경우) 은 가능한 경우가 dp[i-1][0]에서 b을 더한 경우와, dp[i-1][1]에서 b을 더한 경우이다.

 

따라서 각각의 경우의 최솟값을 넣으면 된다,

 

문제 조건에서는 지난 번과 같은 색을 색칠할 수 없기 때문에, r의 경우는 지난 g와 b에서 올 수 밖에 없다.

따라서 dp에 각각 더해지는 값의 최솟값을 넣게 되면, 자연스럽게 그 경우의 최솟값을 구할 수 있게 된다.