링크 : https://www.acmicpc.net/problem/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보다 작거나 같은 자연수이다.
출력 : 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
코드
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
dp = deque([[0]*3 for _ in range(N-1)])
dp.appendleft(list(map(int, input().split())))
for i in range(1, N):
RGB = list(map(int, input().split()))
for color in range(3):
dp[i][color] = RGB[color] + min(dp[i-1][(color+1)%3], dp[i-1][(color+2)%3])
print(min(dp[-1]))
아이디어
현재 단계에 R,G,B를 골랐을 때 최소가 되는 값은, 이전 단계에서 R,G,B를 고르지 않은 값 중 최소값을 골라야 한다.
이전단계(i-1)까지 모든 집이 최소값으로 집을 색칠했고, 마지막에 색칠한 색이 R,G,B인 것을 안다면, 현재 단계(i)에서 최소비용으로 집을 색칠한 방법은 현재 단계가 색칠한 색 R, G, B가 아닌 나머지 두가지 색 중 최소값을 고른다. 이걸 반복적으로 한다.
모든 집에 색을 칠했다면, 마지막 집을 R,G,B로 색칠했을 때의 최소값 3개가 있을텐데, 그 중 가장 작은 값이 모든 집을 최소 비용으로 색칠하는 값이다.
문제를 최적 부분 구조임을 확인하고 이전 값을 저장하고 하는게, 문제를 보고 바로 떠오르면 다행이지만, 다른 문제들을 보니 조금만 꼬아놔도 잘 몰라서.. 좀 더 많이 봐야겠다..
'알고리즘' 카테고리의 다른 글
프로그래머스 - 정수 삼각형 (0) | 2023.01.26 |
---|---|
백준 - 부분합 (0) | 2023.01.09 |
프로그래머스 - 혼자 놀기의 달인 (0) | 2022.12.20 |
프로그래머스 - 모두 0으로 만들기 (0) | 2022.12.19 |
프로그래머스 - 오픈채팅방 (0) | 2022.12.17 |