정보
문제 바로가기 [클릭]
난이도: Silver1
관련 개념: #다이나믹 프로그래밍
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 0.5 초(추가 시간 없음) | 128 MB |
문제
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
입력
1
2
3
4
3
26 40 83
49 60 57
13 89 99
출력
1
96
예제 입출력 2
입력
1
2
3
4
3
1 100 100
100 1 100
100 100 1
출력
1
3
예제 입출력 3
입력
1
2
3
4
3
1 100 100
100 100 100
1 100 100
출력
1
102
예제 입출력 4
1
2
3
4
5
6
7
6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91
출력
1
208
예제 입출력 5
입력
1
2
3
4
5
6
7
8
9
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
출력
1
253
코드(파이썬)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
now = dict(zip(['r', 'g', 'b'], map(int, input().split())))
for _ in range(n-1):
tmp = dict(zip(['r', 'g', 'b'], map(int, input().split())))
tmp['r'] += min(now['g'], now['b'])
tmp['g'] += min(now['b'], now['r'])
tmp['b'] += min(now['r'], now['g'])
now = tmp
print(min(now.values()))
특이사항
- 각각의 색을 선택할 때의 최솟값을 업데이트하는 방식
- 내 코드(30,864KB, 112ms)에 비해 우수한 코드(바로가기, 30,864KB, 68ms)와 비교
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
import sys sys.setrecursionlimit(10**7) n = int(sys.stdin.readline().strip()) cost = [] for i in range(n): cost.append(list(map(int,sys.stdin.readline().strip().split()))) for i in range(1,n): cost[i][0] = min(cost[i-1][1],cost[i-1][2]) + cost[i][0] cost[i][1] = min(cost[i-1][0],cost[i-1][2]) + cost[i][1] cost[i][2] = min(cost[i-1][0],cost[i-1][1]) + cost[i][2] print(min(cost[n-1]))
- 기존: 임시 dict을 생성하고 업데이트
- 개선: 전체 길이 만큼의 리스트 생성 후 업데이트
참고문헌
-
Comments powered by Disqus.