[TIL/크래프톤 정글9기] 31일차(백준 RGB거리 / DP)

DP 문제에 많이 약한거 같아 백준의 단계별 풀어보기에서 DP문제를 풀어보고 있다.
아직까지 DP의 테이블의 초기값과 어떻게 초기화해야 하는지 감이 너무 안잡힌다ㅠ

내가 생각한 DP문제를 풀면서 초반에 중요한 점은 아래 두 가지가 있다.

• 1. DP 테이블를 어떻게 초기화 하며 초기 값을 어떻게 할 것 인가?
• 2. DP 테이블을 기반으로 어떻게 점화식을 작성할 것인가?

RGB거리 문제는 각 집에 색을 칠해야하지만 앞에 칠한 집의 색과 다음 집에 칠해야하는 색이 달라야한다.
일단 입력값이 최대 1000이므로 이중 for문이 된다고 생각해서 dp테이블은 이중 배열이 된다 생각했다.
그럼 dp[i][j]를 어떻게 정의 내릴 것인가가 문제인데, i번째 집까지 고려했을 때, j색으로 칠하는 조합으로 정의를 내렸다.
그 다음 점화식은 3가지가 나오는데, 왜 why? 이전 집에서 빨간색을 고르면 다음 집은 무조건 초록아님 파랑을 칠해야하고, 초록색이면 빨강, 파랑, 파랑색이면 빨강, 초록을 칠해야한다. 그리고 공통적으로 현재 집에 색칠된 값을 더하면 된다.

아이패드 없는 자의 서러움

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
rgb = [list(map(int, input().split())) for _ in range(n)]

# i번째 집까지 고려했을 때, j색으로 칠하는 조합
dp = [([0] * 3) for _ in range(n+1)]
dp[1] = rgb[0]

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

# print(dp)
print(min(dp[n]))

아직까지 다른 DP문제를 볼 때마다 너무 새로워서 계속 익숙해져야겠다 헝헝