[백준/python] 17404_RGB거리2

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

 

 

DP(Dynamic Programming, 동적 계획법)

DP의 사용 조건

• 최적 부분 구조 : 큰 문제를 작은 문제로 분할할 수 있다
• 중복 부분 문제 : 동일한 작은 문제를 반복적으로 해결한다

DP는 한 번 해결했던 문제를 다시금 해결하기 때문에, 메모이제이션(Memoization) 기법을 활용한다. 한 번 계산했던 결과를 dp테이블에 저장해두고, 같은 식을 호출할 때마다 결과만 그대로 가져온다.

 

DP를 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 설정

 

17404_RGB거리2

1149_RGB거리 문제에서 1번 집과 N번 집이 같은 색이면 안된다는 조건이 추가

-> dp테이블의 두 번째 행을 갱신할 때, 첫 번째 행에서 R,G,B 각각을 무조건 선택하도록 설정하기

1) dp테이블을 3개로 만들고,

2) rgb[0][0]일 때 다른 두값(rgb[0][1],rgb[0][2])을 inf로 설정

3) rgb[0][1], rgb[0][2]에 대해 반복

 

 

1. 테이블 정의하기

    D[i][0] : i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 R(빨강)

    D[i][1] : i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 G(초록)

    D[i][2] : i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 B(파랑)

 

2. 점화식 찾기

    D[i][0] = min(dp[i-1][1], dp[i-1][2]) + rgb[i][0]
    D[i][1] = min(dp[i-1][0], dp[i-1][2]) + rgb[i][1]
    D[i][2] = min(dp[i-1][0], dp[i-1][1]) + rgb[i][2]

 

 3. 초기값 설정

    D[0][1] = rgb[0][1], 나머지는 INF

    D[0][2] = rgb[0][2], 나머지는 INF

    D[0][3] = rgb[0][3], 나머지는 INF

 

INF = float('inf')
N = int(input())
rgb = [list(map(int, input().split())) for _ in range(N)]

ans = INF

for i in range(3):
    # RGB 각각에서 출발하는 것을 구현하기 위해서, 해당 색깔에서 출발하는 것이 무조건 최소값이 되게 만든다.
    # R에서 출발하면, G,B 값을 크게 두어 다음 행에서 dp테이블을 갱신할 때 G[0] B[0]를 고려하지 않게 만든다.
    dp = [[INF, INF, INF] for _ in range(N)]
    dp[0][i] = rgb[0][i]
    
    # 중간 부분은 RGB거리1 풀 때와 같다. 현재 집을 칠할 때, 바로 전 집만 고려해주면 된다.
    for j in range(1, N):   
        dp[j][0] = rgb[j][0] + min(dp[j-1][1], dp[j-1][2])
        dp[j][1] = rgb[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = rgb[j][2] + min(dp[j-1][0], dp[j-1][1])
        
    # 마지막 집을 첫번째 집과 다르게 색칠한 두 경우의 비용을 비교하여, for문을 돌며 업데이트한다.
    for k in range(3):
        if i != k:
            ans = min(ans, dp[-1][k])

print(ans)