[Python] 백준 1699 RGB거리

1149번: RGB거리 (acmicpc.net)

1149번: RGB거리

 

코드 작성 1 

n = int(input())
rgb = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*3 for _ in range(n+1)]

for i in range(1,n+1):  #2번째 수부터 n까지
      dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + rgb[i-1][0]
      dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + rgb[i-1][1]
      dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + rgb[i-1][2]
      
print(min(dp[n][0],dp[n][1],dp[n][2])) #인덱스는 1 ~ n

 

코드 작성 2 

n = int(input())
dp = [list(map(int, input().split())) for _ in range(n)]

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][0], dp[n-1][1], dp[n-1][2])) #인덱스는 0 ~ n-1

 

코드  풀이

#1 코드의 이해

(1) Red, Green, Blue 각각의 값을 dp 테이블에  dp[n] = [0,0,0] 으로 세팅하고,

(2) n번째에 Red가 나오려면 n-1번째에는 Green 또는 Blue의 값이 되어야 하므로 rgb[n-1][1] 또는 rgb[n-1][2] 의 값이 된다.

(3) 즉 dp테이블(누적된 최소값)에는 dp[n][0] = min[dp[n-1][1], dp[n-1][2]) + rgb([n-1][0])의 값이 된다.

 

#2 코드의 이해

당초 입력 값을 dp값이면서 동시에 for를 이용하여 계속 업데이트 한다.

 dp[i]  =   dp[i-1]  +  dp[i] 

 [i]까지 누적 값  =  [i-1]까지 누적 값  +  [i]의 입력값