[백준/1149/파이썬] RGB거리

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

1149번: RGB거리

Problem

• RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
• 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.
• 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

조건

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

SOL

완전탐색

• 이 문제도, 언뜻보면 DFS로 완전탐색, 경로 구하는 문제아니야!? 할 수 있다.
• 경로를 구하는건 맞지만, 최적화가 필요한 경로 구하기이다.
• 자기가 있던 색깔로는 다시 못가므로, 한 경로를 갈 때마다, 2가지 경우가 생기게 된다.
• 완전탐색으로 한다면, O(2^n)이 걸린다. => 2^1000 불가능!

DP

• DP[y][x] = 색을 칠했을 때, 최소 비용들을 저장한 배열
• 구하는 값: min(DP[N])
• 초기값: DP[0] = board[0]
• 점화식: DP[y][0] = min(DP[y-1][1],DP[y-1][2])+board[y][0] , DP[y][1] = min(DP[y-1][0],DP[y-1][2])+board[y][1] ,  DP[y][2] = min(DP[y-1][0],DP[y-1][1])+board[y][2]

import sys
input= sys.stdin.readline
N = int(input().rstrip())
board=[list(map(int,input().split())) for _ in range(N)]
DP = [[0]*3 for _ in range(N)]

DP[0] =board[0]
#print(DP)

for i in range(1,N):
    DP[i][0] = min(DP[i-1][1],DP[i-1][2])+board[i][0]
    DP[i][1] = min(DP[i-1][0],DP[i-1][2])+board[i][1]
    DP[i][2] = min(DP[i-1][0],DP[i-1][1])+board[i][2]

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