[백준] 17404번(RGB거리 2)

백준 17404번

최종 제출 코드

import sys

input = sys.stdin.readline
n = int(input().rstrip())
array = list(list(map(int, input().split())) for i in range(n))
dp = [[0,0,0] for i in range(2)]

max_value = 1000001

for j in range(3):
  dp[0][0] = 1000001
  dp[0][1] = 1000001
  dp[0][2] = 1000001

  dp[0][j] = array[0][j]

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

    dp[0][0] = dp[1][0]
    dp[0][1] = dp[1][1]
    dp[0][2] = dp[1][2]

  max_value = min(max_value, min(dp[0][(j+1)%3], dp[0][(j+2)%3]))

print(max_value)

코드 출처

.
◼ 하나의 색으로 시작해서 각각의 색으로 끝나는 케이스를 모두 고려

• 시작색과 끝색이 다른 경우의 최소값을 max_value에 업데이트

.
◼ 초기화값?

• 참고코드에는 dp의 초기값을 1000 * 1000 * 10으로 설정
• 왜 저런 값으로 설정했는지 모르겠어서 임의로 1000으로 변경했더니 오답처리
• 문제 조건을 잘 읽어보니 각 색의 비용은 최대 1000이고, 케이스도 1000개가 최대
  ⇒ 초기값이 1000 * 1000보다는 커야함
  ⇒ 초기값을 1000001로 설정했더니 정답