RGB거리 성공
0.5 초 (추가 시간 없음) | 128 MB | 113629 | 63845 | 47407 | 55.288% |
문제
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보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
예제 입력 1 복사
3
26 40 83
49 60 57
13 89 99
예제 출력 1 복사
96
예제 입력 2 복사
3
1 100 100
100 1 100
100 100 1
예제 출력 2 복사
3
예제 입력 3 복사
3
1 100 100
100 100 100
1 100 100
예제 출력 3 복사
102
예제 입력 4 복사
6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91
예제 출력 4 복사
208
예제 입력 5 복사
8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19
예제 출력 5 복사
253
처음 문제를 풀땐 이동 방향을 생각해야된다 생각해서 여러 풀이를 떠올렸다.
뒤에서부터 차례대로 작은걸 고르기, 앞에서부터 작은걸 고르기 그리고 뽑을것과 그 다음것을 생각해서 더 적절한 수 고르기 등등... 여러 알고리즘을 세우고 풀어봤지만 풀리지 않은 문제다.
잠시 쉬다가 다시 문제를 봤는데 다이나믹프로그래밍 기법이 기억났다. 쉽게 풀어쓰자면 이전 계산값을 재활용하는 기법이다.
코드를 전부 지우고 다시 작성하기 시작했다.
일단 dp 리스트를 필요한 크기만큼 만들어주고 첫번째 요소는 입력값 그대로 저장. 두번째 요소부터는 입력값이 3개이니깐 각각 자기 자리 이외의 자리들과 더해서 최소값인 요소를 temp에 저장시키기로 했다.
1번 예제를 그림으로 보면 다음과 같다.
이와 같은 로직으로 풀면 된다.
#1149 RGB거리 (다이나믹프로그래밍)
import sys
n = int(sys.stdin.readline())
dp = [0] * n
for i in range(n): #입력 받기
x,y,z = map(int, sys.stdin.readline().split())
now = [0,0,0]
if i == 0:
dp[0] = [x,y,z]
else:
#더하기
if dp[i-1][1] + x < dp[i-1][2] + x: #작은 값을 찾아서 저장
now[0] = dp[i-1][1] + x
else:
now[0] = dp[i-1][2] + x
if dp[i-1][0] + y < dp[i-1][2] + y:
now[1] = dp[i-1][0] + y
else:
now[1] = dp[i-1][2] + y
if dp[i-1][0] + z < dp[i-1][1] + z:
now[2] = dp[i-1][0] + z
else:
now[2] = dp[i-1][1] + z
dp[i] = now
print(dp)
print(min(dp[n-1]))
https://www.acmicpc.net/problem/1149