[알고리즘] 백준 1149번 문제

date

Nov 5, 2023

slug

dp-1

author

status

Public

1149번 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.

N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.


import sys
input = sys.stdin.readline
n=int(input())
dp = []
for i in range(n):
    dp.append(list(map(int, input().split())))
for i in range(1,n):
    dp[i][0]= min(dp[i-1][1], dp[i-1][2])+dp[i][0]
    dp[i][1]= min(dp[i-1][0], dp[i-1][2])+dp[i][1]
    dp[i][2]= min(dp[i-1][1], dp[i-1][0])+dp[i][2]
print(min(dp[n-1]))

풀이

i번째 집이 빨강이면→ i-1번째는 초록, 파랑 가능

i번째 집이 초록이면→ i-1번째는 빨강, 파랑 가능

i번째 집이 파랑이면→ i-1번째는 초록, 빨강 가능

따라서, 배열에 리스트 형식으로 입력받은 후,

상향식 dp로 풀었다.

첫번째 집은 i-1번째 적용이 불가하므로 두번째 집부터 dp반복 시작.

두번째 집에서 빨강, 초록, 파랑으로 칠하는 경우를 전부 구한다. (n번째 집까지 반복)

두번째 집이 빨강인 경우 = 첫번째 집이 파랑인 경우와 초록인 경우 중 더 작은 값 + 두번째 집의 빨강 값

두번째 집이 초록인 경우 = 첫번째 집이 파랑인 경우와 빨강인 경우 중 더 작은 값 + 두번째 집의 초록 값

두번째 집이 파랑인 경우 = 첫번째 집이 빨강인 경우와 초록인 경우 중 더 작은 값 + 두번째 집의 파랑 값

결국, 구하려는 집의 빨강, 파랑, 초록인 경우의 값을 모두 구할 수 있다. 그 중에서 가장 작은 값을 출력하는게 답이다.

[알고리즘] 백준 1149번 문제 - DP

1149번 문제

입력

출력

풀이