백준 17404번: RGB 거리 2 (Python)

접근

단계별 문제 '동적계획법3' 이전 문제들에서 비트마스크를 이용한 문제들을 푸느라 이 문제도 비트마스크 문제인 줄 알고 억지로 비트마스크를 쓰려고 했던 것이 발목을 잡아 결국 문제 해결을 늦추었다. 앞으로 이런 실수는 없어야겠다.

오히려 이전에 풀었던 RGB 거리 DP 문제와 매우 유사했던 문제였다.

RGB 거리 기본 문제: 2021.03.27 - [코딩/백준 (Python)] - 백준 1149번: RGB 거리 (Python)

백준 1149번: RGB 거리 (Python)

하지만 이번에는 집들이 원형으로 배열되어있어 첫번째 집과 마지막 집이 색이 달라야 했던 점이 차이를 가진다.

이전 RGB 문제와 동일하게 DP 문제를 해결하되, 아래와 같은 방법으로 생각하여 문제를 해결하였다.

1. 첫번째 집이 R, G, B 각각의 색을 가질 때를 기준으로 총 3번의 연산을 진행한다.
2. 첫번째 집이 R 일 때, 마지막 집이 R 인 경우를 뺀 최소값을 기억한다.
3. 마찬가지로 첫번째 집이 G, B 일 때 마지막 집들의 최소값들을 비교하여 최종 결과를 얻는다.

코드

import sys

INF = float('inf')
n = int(sys.stdin.readline())
cost = []
for i in range(n):
    r, g, b = map(int, sys.stdin.readline().split())
    cost.append([r, g, b])
minVal = INF

for i in range(3):
    dp = [[0 for _ in range(3)] for _ in range(n)]

    for j in range(3):
        if j == i:
            dp[0][j] = cost[0][j]
            continue
        dp[0][j] = INF

    for j in range(1, n):
        dp[j][0] = cost[j][0] + min(dp[j - 1][1], dp[j - 1][2])
        dp[j][1] = cost[j][1] + min(dp[j - 1][0], dp[j - 1][2])
        dp[j][2] = cost[j][2] + min(dp[j - 1][0], dp[j - 1][1])

    for j in range(3):
        if j == i:
            continue
        minVal = min(minVal, dp[-1][j])

print(minVal)
import sys

INF = float('inf')
n = int(sys.stdin.readline())
cost = []
for i in range(n):
    r, g, b = map(int, sys.stdin.readline().split())
    cost.append([r, g, b])
minVal = INF

for i in range(3):
    dp = [[0 for _ in range(3)] for _ in range(n)]

    for j in range(3):
        if j == i:
            dp[0][j] = cost[0][j]
            continue
        dp[0][j] = INF

    for j in range(1, n):
        dp[j][0] = cost[j][0] + min(dp[j - 1][1], dp[j - 1][2])
        dp[j][1] = cost[j][1] + min(dp[j - 1][0], dp[j - 1][2])
        dp[j][2] = cost[j][2] + min(dp[j - 1][0], dp[j - 1][1])

    for j in range(3):
        if j == i:
            continue
        minVal = min(minVal, dp[-1][j])

print(minVal)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!