[백준] 17404번 RGB거리2 (파이썬, DP) feet. 인간적인 코딩

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

17404번: RGB거리 2

 

개인적으로는 dp 문제가 제일 어렵다.

다른 사람의 코드를 봐도 점화식을 이해하는게 버겁기 때문이다.

 

참고로 rgb거리2의 점화식을 이해하기 위해서는 우선

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

1149번: RGB거리

rgb거리를 푸는 것이 좋다.

 

내가 오늘 글에 쓰고 싶은 것은 점화식이 포인트가 아니다.

다른 사람들의 정갈한 풀이를 이해하지 못해서 인간적인 모습의 코드를 풀어서 포스팅을 한다.

 

해당 문제의 점화식 코드는 다음과 같다.

 

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

 

해당 점화식을 이해하고 있다는 가정하에 포스팅을 진행하겠다.

 

이번 문제는 맨 앞집과 끝 집의 색깔이 달라야한다는 조건이 추가되었다.

dp는 애초에 누적된 비용이 들어가 있음으로 첫번째 집이 어떤 색깔로 색칠했는지를 알지 못한다는 단점이 있다.

(아마 이 부분을 해결하라는 의미의 문제일 것이다.)

 

백준 문제 해설에 대한 블로그 들의 치명적인 단점이 있는데 서로 참고해서 푸는 경우가 많다보니

글들이 최적화된 코드 1가지 모양으로 모인다는 것이다.

꼭 나쁘다고는 할 수 없지만 나는 이번 문제의 해답 코드가 이해가 잘 안갔다.

그래서 그걸 이해하고 따라하기 보다는 그냥 내가 생각하는데로 인간적인 면모의 코드를 작성했다.

포인트는 다른 사람들과 같다.

 

1. 경우의 수는 결국 3가지다. (첫번째 집이 빨강, 초록, 파랑인 경우)

2. 첫번째 집이 빨강일때는 마지막 집은 초록과 파랑 중 베스트를 찾아야하고 초록일때는 마지막 집이 빨강과 파랑 중 ...

3. 마지막 집의 경우의 수도 3가지이며 그 중 가장 최소 비용인 경우를 찾으면 된다.

 

이 3가지 중요한 점을 코드로 풀어서 적음면 끝이다.

 

1번 같은 경우는 첫번째 집이 빨강이라면 파랑일때와 초록일때의 비용을 1001로 지정하면 된다.(1001로 해도 크게 예외 없이 정답처리된다.)

 

첫번째 집이 빨강색일 때의 경우를 구해보면

dp[0][0] = arr[0][0]
dp[0][1] = 1001
dp[0][2] = 1001
for i in range(1, n-1):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
    dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + arr[i][2]

red = min(min(dp[n-2][0], dp[n-2][2]) + arr[n-1][1],
          min(dp[n-2][0], dp[n-2][1]) + arr[n-1][2])

 

이런 식으로 구할 수 있다.

 

이렇게 초록일 때와 파랑일 때도 구해주면 끝이다.

 

전체 코드를 보면 이 글에서 말하고자 하는 바가 무엇인지 파악할 수 있을 것이다.

 

import sys

n = int(sys.stdin.readline())

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

arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp[0][0] = arr[0][0]
dp[0][1] = 1001
dp[0][2] = 1001
for i in range(1, n-1):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
    dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + arr[i][2]

red = min(min(dp[n-2][0], dp[n-2][2]) + arr[n-1][1],
          min(dp[n-2][0], dp[n-2][1]) + arr[n-1][2])

dp[0][0] = 1001
dp[0][1] = arr[0][1]
dp[0][2] = 1001
for i in range(1, n-1):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
    dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + arr[i][2]

green = min(min(dp[n-2][1], dp[n-2][2]) + arr[n-1][0],
            min(dp[n-2][0], dp[n-2][1]) + arr[n-1][2])

dp[0][0] = 1001
dp[0][1] = 1001
dp[0][2] = arr[0][2]
for i in range(1, n-1):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
    dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + arr[i][2]

blue = min(min(dp[n-2][1], dp[n-2][2]) + arr[n-1][0],
           min(dp[n-2][0], dp[n-2][2]) + arr[n-1][1])

print(min(red, green, blue))

 

남들은 for문을 3번 돌리면서 간결한 코드로 만들었던데 나는 그냥 이렇게 풀었다.

이 편이 내 자신이 이해하기 쉬웠기 때문이다.