공부 자료/알고리즘
(Python/파이썬) 백준 1149번 - RGB거리
뚜루뚜루세니
2021. 8. 3. 10:08
728x90
문제출처: https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
1. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
n = int(input())
R,G,B = 0,1,2
#각 집 마다 색깔별 가격
RGB = [list(map(int, input().split()))for i in range(n)]
#같은 색 연달아 불가
#현재가 R이면 GB 중 작은 값으로
# RGB[i][R] = i번째 집을 R
# RGB[i][G] = i번째 집을 G
# RGB[i][B] = i번째 집을 B
for i in range(1,n):
RGB[i][R]=RGB[i][R]+min(RGB[i-1][G],RGB[i-1][B])
RGB[i][G]=RGB[i][G]+min(RGB[i-1][R],RGB[i-1][B])
RGB[i][B]=RGB[i][B]+min(RGB[i-1][G],RGB[i-1][R])
#빨강, 초록, 파랑으로 칠하는 경우 중 최소값 출력
print(min(RGB[n-1]))
|
cs |
2. 해결과정
앞집에 대해서 색깔이 겹치지 않게 배치하는 것이 중요했던 문제였다.
처음에 각 집에 대한 색깔별 가격을 입력 받고, 반복문을 통해 2번째 집 부터 세가지 색상을 칠할 때의 상황을 고려해주면 된다.
결과적으로 RGB[n-1]칸에는 첫번째 집을 R로 칠했을 때 결과값, G로 칠했을 때 결과값, B를 선택했을 때 결과값이 담겨져 있고 그 중 가장 작은 값을 출력해주면 된다.
3. 느낀점
dp 어렵다.. 점화식을 찾아내는 것이 까다롭다.
728x90