[BOJ/python] 1149: RGB거리

문제

✔️ silver 1
다이나믹 프로그래밍

문제 흐름

바로 주의해야할 점부터 얘기해보자면 두가지(또는 그 이상)의 컬러의 비용이 같다면 이 둘중 어느쪽을 선택하는지가 선택지가 또 갈리게 된다는 점이다!
아래는 질문게시판에서 찾은 반례인데, 말이 이상해서 이해가 안된다면 이를 참고하면 좋을 것 같다.

4
5 4 3
1 1 2
1 5 1
5 3 2
output: 8
correct answer: 7

4
1 4 3
4 1 1
1 2 3
3 5 5
output: 8
correct answer: 7

4
4 1 5
2 1 3
3 4 5
5 1 3
output: 9
correct answer: 8

4
3 3 2
3 2 5
5 2 2
4 3 1
output: 9
correct answer: 8

4
4 4 4
2 4 1
2 4 2
1 3 3
output: 10
correct answer: 9

이 반례를 처음 보고 내 코드가 정확하게 output값(오답;;)이 출력되어서 너무 당황했다.
나름 예제 입력은 다 정답을 출력했었는데!

처음의 방법은 다음과 같았다. (어차피 오답인 풀이이니 신경 안써도 된다.)

1. 2차원 배열 cost에 입력받은 각 집별 페인트 비용들을 저장한다.
2. 1차원 dp배열 paint를 준비한다. (계산값 저장)
3. paint[0]에 0번째 집을 칠하는 가장 적은 값인 cost[0]의 최솟값을 저장한다.
4. 1번째 집부터 다음을 반복한다.
   a) i-2번째 집에서 사용된 컬러의 idx를 제외한 i-1번째 집의 최솟값을 고르고, i번째 집의 최솟값을 고른다.
   b) a에서 찾은 두 값의 idx가 일치한다면 i-1의 2번째 작은값 + i의 최솟값, i-1의 최솟값 + i의 2번째 작은값 을 비교해서 적은 값을 paint[i]에 저장한다.

그러니까 paint[i]에 i번째 집까지 칠하는 최소 비용을 저장한 셈인데, 앞서 말한 경우 i-3번째 집부터 확인해서 수정해야하는데 그게 가능하지 않은 방법이다.

---

그리고 gpt한테 이번에도 힌트를 달라고 했다. ^^
그리고 얻은 정답 풀이는 다음과 같다.

1. 2차원 배열 cost에 입력받은 각 집별 페인트 비용들을 저장한다.
2. 2차원 dp배열 paint를 준비한다. (계산값 저장)
   여기서 paint[i][0], paint[i][1], paint[i][2]는 각각 i번째 집을 빨강, 초록, 파랑으로 칠할 경우 현재까지 집을 칠하는 최소 비용이다.
3. paint[0]에 0번째 집을 각 컬러로 칠하는 최소비용인 cost[0]값들을 넣어준다.
4. 1번째 집부터 다음을 반복한다.
   a) i번째 집을 0번(Red)로 칠한다면 i-1번째 집은 1번(Green) 또는 2번(Blue)로 칠해야하므로, paint[i-1][1]과 paint[i-1][2]중 적은 값을 구하고 이에 cost[i][0]을 더한 값을 paint[i][0]에 저장한다.
   b) i번째 집의 다른 컬러에 대해서도 a의 과정을 반복한다.

코드

# RGB거리
# dp

import sys
input = sys.stdin.readline

def dp (cost: list):
    n = len(cost)
    paint = [[0, 0, 0] for i in range(n)]
    paint[0][0] = cost[0][0]
    paint[0][1] = cost[0][1]
    paint[0][2] = cost[0][2]

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

    # print(cost)
    # print(paint)
    return min(paint[-1])


if __name__ == "__main__":
    n = int(input())
    cost = []
    for i in range(n):
        c = list(map(int, input().split()))
        cost.append(c)
    
    result = dp(cost)
    print(result)

마무리

솔직히 이번 문제는 gpt가 다 풀어줬다.
힌트만 얻어가려고 했는데 완전히 풀이를 다 주고 그대로 조합해서 완성만 내가 한 느낌이랄까 ㅠㅠ
근데 풀이를 보고 느낀게 내가 내 머리로 이 방법을 생각해내지 못했겠구나, 그냥 풀이를 읽어보고 이해하고 배워가는게 낫겠다 싶었다.

반례