[python] 1149: RGB거리

1149: RGB거리

나의 접근법

3
26 40 83
49 60 57
13 89 99

1번 집의 최솟값은 26, 2번 집의 최솟값은 49. 3번 집을 13으로 선택한다고 하면 답은 되는데, 이 경우를 어떻게 다 구하지? 내가 생각한 풀이법은 O(NN)이 된다.

코드 설명

이게 어떻게 DP랑 연관이 되는 건진 전혀 모르겠다🫡 앞에 계산된 값에 영향을 받으면 DP를 하면 되는 건가.

거쳐야 하는 생각

1. 최솟값으로만 계산하려니까 안 되네?
2. (테이블 구성) 그럼 색에 대해 정보를 넣어야겠군🎨
3. 점화식을 구해야 하는데 모를 땐 일단 적어보자.

예시

• 집이 1개.

  • input

  1
  26 40 83

  • DP
    집이 하나밖에 없으니까 어떤 색으로 칠하든 마음대로 할 수 있다.

  0  1  2
  26 40 83

• 집이 2개.

  • input

  2
  26 40 83
  49 60 57

  • DP
    생각해야 할 앞집이 생겼다. 2번 집이 R일 때는 앞집이 R이면 안 된다.

  0  1  2
  26 40 83
  min(40,83) + R / min(26,83) + G / min(26,40) + B

• 집이 3개.

  • input

  3
  26 40 83
  49 60 57
  13 89 99

  • DP
    3번 집이 R일 때는 앞집이 R이면 안 된다.

  0  1  2
  26 40 83
  min(40,83) + R / min(26,83) + G / min(26,40) + B
  min(앞집 G, 앞집 B) + R / ... 

점화식

DP[i][색] = min(DP[i-1][다른 색], DP[i-1][또 다른 색]) + 색

점화식을 생각해낸 나에게 칭찬의 박수🙌

코드

import sys
input = sys.stdin.readline

COLOR_SIZE = 3
HOUSE_MAX_SIZE = 1001


def getMinPrice() -> int:
    DP = [[0 for _ in range(COLOR_SIZE)] for _ in range(HOUSE_MAX_SIZE)]
    DP[1][0] = colors[1][0]
    DP[1][1] = colors[1][1]
    DP[1][2] = colors[1][2]

    for house in range(2, houses+1):
        DP[house][0] = min(DP[house-1][1], DP[house-1][2]) + colors[house][0]
        DP[house][1] = min(DP[house-1][0], DP[house-1][2]) + colors[house][1]
        DP[house][2] = min(DP[house-1][0], DP[house-1][1]) + colors[house][2]

    return min(DP[houses])


houses = int(input().rstrip())
colors = [[0, 0, 0]] + [list(map(int, input().rsplit()))
                        for _ in range(houses)]
print(getMinPrice())

참고 자료

바킹독 선생님은 설명을 정말 잘하신다