[백준] 17404 : RGB 거리 2 (파이썬)

DP 문제

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

---

문제 요약

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

---

💡 풀이 코드 (실패 - 마지막 행을 0번째 행으로 옮겨 겹치지 않게 하는 코드)

'''
5
1 10 100
1 10 100
1 10 100
1 10 100
1 10 100
출략 : 32
정답 :122

'''
# 마지막 행을 0번째 행으로 옮겨 겹치지 않도록 하자.
import sys 
n = int(sys.stdin.readline())
graph = [[0] * 3 for _ in range(n + 1)]
dp = [[0] * 3 for _ in range(n + 1)]

for i in range(1, n + 1):
    graph[i][0], graph[i][1], graph[i][2] = map(int, sys.stdin.readline().split())    
    if i == n:
        dp[0][0],dp[0][1],dp[0][2] = graph[i][0], graph[i][1], graph[i][2]

def sol(n, graph):
    for i in range(1, n):
        for j in range(3):
            dp[i][j] = min(dp[i - 1][j - 1] + graph[i][j], dp[i - 1][j - 2] + graph[i][j])

    if dp[0].index(min(dp[0])) == dp[n-1].index(min(dp[n-1])):
        minIdx = dp[n-1].index(min(dp[n-1]))
        dp[n - 1][minIdx] = sys.maxsize
    print(min(dp[n-1]))

sol(n, graph)

 

주요 로직

• n번째 행을 0번째 행(1번째 행 바로 위)로 옮겨 겹치지 않도록 하자.
  • 현재 비용의 최솟값을 선택하는 점화식이, 앞 집에서 사용했던 색을 제외한 나머지 색 중 하나를 선택하기 때문에 이러한 접근이 가능하다고 판단했다.

if i == n:
    dp[0][0],dp[0][1],dp[0][2] = graph[i][0], graph[i][1], graph[i][2]

• n번째 행을 0번째 행으로 옮겨줌에 따라 즉, 마지막 집을 0번째 집으로 옮겨줌에 따라 발생하는 예외 처리를 해주자.
  • 0번째 행으로 옮겨간 마지막 집(n)의 색깔이 마지막 직전 집(n-1)의 색깔과 겹치면 안된다.
  • 따라서 만약, 0번째 집을 칠할 시 비용의 최솟값을 가지게 되는 색과 n-1번째 집을 칠할 시 비용의 최솟값을 가지게 되는 색이 같다면, 해당 색이 선택되지 않도록 sys.maxsize로 만들어주었다.
  • 그렇다면, 0번 집과 n-1번 집이 겹치는 색을 제외하고, 마지막이 된 n-1번 집을 나머지 두 색 중 하나로 칠했을 때의 최솟값을 출력할 수 있을 것이다.

if dp[0].index(min(dp[0])) == dp[n-1].index(min(dp[n-1])):
    minIdx = dp[n-1].index(min(dp[n-1]))
    dp[n - 1][minIdx] = sys.maxsize
print(min(dp[n-1]))

 

틀린 이유

다음과 같은 경우에 오답을 출력한다.

5
1 10 100
1 10 100
1 10 100
1 10 100
1 10 100
출략 : 32
정답 :122

---

💡 풀이 코드 (성공)

import sys 
n = int(sys.stdin.readline())
graph = [[0] * 3 for _ in range(n + 1)]
dp = [[0] * 3 for _ in range(n + 1)]

for i in range(1, n + 1):
    graph[i][0], graph[i][1], graph[i][2] = map(int, sys.stdin.readline().split())    
def sol(n, graph):
    ans = sys.maxsize
    for t in range(3):
        dp[1][0],dp[1][1],dp[1][2] = 10000,10000,10000
        dp[1][t] = graph[1][t]

        for i in range(2, n + 1):
            for j in range(3):
                dp[i][j] = min(dp[i - 1][j - 1] + graph[i][j], dp[i - 1][j - 2] + graph[i][j])
        dp[n][t] = sys.maxsize
        ans = min(ans, min(dp[n]))
    print(ans)
sol(n, graph)

 

dp[i][j] = i번째 집을 j번째 색으로 칠할 때의 비용의 최솟값 

 

주요 로직

• 1번 집을 칠할 때 사용할 색깔을 미리 지정해놓자. 
  • 색깔이 RGB 3가지이므로 가장 바깥쪽 루프에 for문(3)을 두어 1번 집을 칠할 때 사용할 색깔을 각각 지정해주자.
  • 우리는 최소 비용을 구하는게 목적이므로, 1번 집을 RGB 각각의 색으로 칠할 때의 비용의 최솟값을 10000으로 초기화해준다. 그 후, 이번 루프에서 사용할 색깔(t)의 dp값만 실제 비용으로 할당해준다면 1번 집을 무조건 t색으로 칠하는 것이 보장된다.

for t in range(3):
    dp[1][0],dp[1][1],dp[1][2] = 10000,10000,10000
    dp[1][t] = graph[1][t]

• n번 집을 칠할 때, 1번 집에서 사용했던 색이 선택되지 않도록 하자.
  • 1번 집에서 사용했던 색이 선택되어 사용되는 것을 방지하기 위해 dp[n][t]를 sys.maxsize로 만들어준다.
  • 그렇다면, 1번 집에서 선택했던 색을 제외하고, n번 집을 나머지 두 색 중 하나로 칠했을 때의 최솟값을 ans에 저장할 것이다.

dp[n][t] = sys.maxsize
ans = min(ans, min(dp[n]))