[Algorithm] 1149. RGB

1149: RGB(DP)

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

• 문제 티어 : S1
• 풀이 여부 : Solved
• 소요 시간 : 22:38

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().rstrip().split())) for _ in range(N)]

dp = [[0]*3 for _ in range(N)]
dp[0] = arr[0] # base case

for i in range(1, N): # 현재 열 제외, i-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][0], dp[i-1][1]) + arr[i][2]

print(min(dp[N-1]))

접근 방식

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

문제를 이해하는 데 한참 걸렸지만, 궁극적으로 현재의 집이 이전 집과 다음 집의 색상과 겹치면 안된다는 의미다.

값을 누적해나가며 최솟값을 계산하는 문제이므로 DP로 풀이

N개의 줄에 R, G, B 최솟값을 저장할 것이기에 DP테이블을 행 당 3개의 정수를 저장할 수 있는 N개의 줄로 구성

base case를 arr[0]으로 두며,

1 ~ N-1까지의 집을 순회하며 현재 열을 제외하고 i-1행의 열 중 최솟값과 현재 칸의 값을 더하며 DP테이블을 채워간다.

배운점 또는 느낀점