[백준/파이썬] 1149 RGB거리
https://www.acmicpc.net/problem/1149
알고리즘 분류
- 다이나믹 프로그래밍
문제풀이
처음에 0번 집에서 최소값을 가지는 색깔을 선택해서 풀었는데
다음과 같은 반례 때문에 실패했다.
ex)
2
100 1 100
999 1 999 -> 101이 나와야함
1번 집에서 R를 선택했을 경우 0번 집은 G,B중에서 최소값을 선택했을 것이다. 그 값과 원래 값을 계속해서 합산해나간다.
1번 집에서 G를 선택했을 경우 0번 집은 R,B중에서 최소값 선택...
ex)
49=min(40,83)+49=89
60=min(26,83)+60=86
57=min(26,40)+57=83
26 40 83
49 60 57
13 89 99
↓
26 40 83
89 86 83
13 89 99
소스코드
n=int(input())
cost=[]
for i in range(n):
cost.append(list(map(int, input().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]))
참고: https://pacific-ocean.tistory.com/147
Author And Source
이 문제에 관하여([백준/파이썬] 1149 RGB거리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bye9/백준파이썬-1149-RGB거리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)