알고리즘/백준
동적 프로그래밍 : RGB거리(백준 1149번)
bewisesh91
2021. 12. 1. 15:30
728x90
▶ 문제 : https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
##### 문제 #####
# 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보다 작거나 같은 자연수이다.
##### 출력 #####
# 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
▶ 접근 방법
점화식 연습에 도움이 되는 문제였다.
N번째 집을 기준으로 했을 때, 문제 요구 조건을 어떻게 충족할 수 있을지 고민하는 것이 관건이었다.
▶ 풀이 코드
import sys
N = int(sys.stdin.readline().rstrip())
house_info = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
DP = [[0] * 3 for _ in range(N)]
for house in house_info:
print(house)
print()
for i in range(N) :
if i == 0:
DP[i] = house_info[i]
else :
DP[i][0] = house_info[i][0] + min(DP[i-1][1], DP[i-1][2])
DP[i][1] = house_info[i][1] + min(DP[i-1][0], DP[i-1][2])
DP[i][2] = house_info[i][2] + min(DP[i-1][0], DP[i-1][1])
for i in DP :
print(i)
print(min(DP[-1]))
▶ 관련 링크
2021.11.25 - [알고리즘] - 동적 프로그래밍(Dynamic Programming)이란?
2021.11.25 - [알고리즘] - 동적 프로그래밍 : 피보나치 수 2(백준 2748번)
2021.11.25 - [알고리즘] - 동적 프로그래밍 : 01타일(백준 1904번)
2021.11.26 - [알고리즘] - 동적 프로그래밍 : 평범한 배낭(백준 12865번)
2021.11.27 - [알고리즘] - 동적 프로그래밍 : 동전(백준 9084번)
2021.11.27 - [알고리즘] - 동적 프로그래밍 : LCS(백준 9251번)
2021.11.27 - [알고리즘] - 동적 프로그래밍 : 가장 긴 증가하는 부분 수열(백준 11053번)
2021.11.29 - [알고리즘] - 동적 프로그래밍 : 점프(백준 2253번)