[백준1149번][백준][baekjoon][1149번][DynamicProgramming][DP][RGB거리][Python][파이썬]

문제링크

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

1149번: RGB거리

문제

 

풀이

전형적인 DP문제입니다. 세 가지 색상을 가지고 있으며, 이웃집(i-1, i+1)과 같은 색을 가질 수 없는 조건이 주어진 문제입니다. 다양한 접근 방법이 있을 수 있지만 저는 2차원 배열을 사용하였습니다. 행은 N번째 집을 나타내며 열은 칠하고자 하는 색(R, G, B)을 나타냅니다. 즉 DP[N][2]는 N번째 집을 B(Blue)로 칠했을 때의 최소 비용입니다. N번째 집에 원하는 색을 칠할 때는 제한조건을 만족해야 합니다. 만약 N번째 집을 R(Red)로 칠하고 싶다면 N-1번째 집은 G(Green) 또는 B(Blue)로 칠했을 때만 가능합니다. 이중 최소 비용을 구하는 방법은 아래와 같습니다.

 

N번째 집을 R(Red)로 칠하는 최소비용 D[N][0]  =

  1) N-1번째 집을 G(Green)로 칠하는 최소 비용 : D[N-1][1]

  2) N-1번째 집을 B(Blue)로 칠하는 최소 비용 : D[N-1][2]

 

1), 2) N-1번째 집에 G, B 중 더 적은 비용이 든 경우에서 N번째 집을 R로 칠하는 비용을 더하면 N번째 집을 R로 칠하는 최소비용을 구할 수 있습니다. 이를 점화식으로 나타내면 다음과 같습니다. 설명의 편의상 N번째에 R을 칠하는 비용을 Red, G를 칠하는 경우를 Green, B를 칠하는 경우를 Blue로 표현하겠습니다.

 

D[N][0]= if D[N-1][1] > D[N-1][2] : D[N-1][1]+Red

            else : D[N-1][2]+Red 

D[N][1]= if D[N-1][0] > D[N-1][2] : D[N-1][0]+Green

            else : D[N-1][2]+Green

D[N][2]= if D[N-1][0] > D[N-1][1] : D[N-1][0]+Blue

            else : D[N-1][1]+Blue

 

소스코드

#Python

 

testcase=int(input())
 
cost=[ [0,0,0] for _ in range(1001)]
 
dp=[ [0,0,0] for _ in range(1001) ]
 
for i in range(testcase):
    costline=input()
    cost[i][0]=int(costline.split(' ')[0])
    cost[i][1]=int(costline.split(' ')[1])
    cost[i][2]=int(costline.split(' ')[2])
 
    if i==0:
        dp[i][0]=cost[i][0]
        dp[i][1]=cost[i][1]
        dp[i][2]=cost[i][2]
    else:
        if dp[i-1][1]+cost[i][0] < dp[i-1][2]+cost[i][0]:
            dp[i][0]=dp[i-1][1]+cost[i][0]
        else: 
            dp[i][0]=dp[i-1][2]+cost[i][0]
 
        if dp[i-1][0]+cost[i][1] < dp[i-1][2]+cost[i][1]:
            dp[i][1]=dp[i-1][0]+cost[i][1]
        else: 
            dp[i][1]=dp[i-1][2]+cost[i][1]
    
        if dp[i-1][0]+cost[i][2] < dp[i-1][1]+cost[i][2]:
            dp[i][2]=dp[i-1][0]+cost[i][2]
        else: 
            dp[i][2]=dp[i-1][1]+cost[i][2]
 
    
minnum=sorted(dp[testcase-1])
print(minnum[0])

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.

이번 포스팅에서는 python으로 작성하였지만, 추후 C와 C++ 코드도 올리도록 하겠습니다.