취준생의 코딩테스트 연습기

[백준] 1149번 RGB거리 / 파이썬(python) 본문

코딩테스트/백준

[백준] 1149번 RGB거리 / 파이썬(python)

Jiwon_C 2021. 5. 23. 16:12

# 문제 링크

https://www.acmicpc.net/problem/1149

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

# Soultion

점화식을 찾아 DP방법으로 해결함

현재위치(빨) = 이전위치(파)+이전위치(초) 이런 식으로 진행된다.

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
li = []
for _ in range(n):
    li.append(list(map(int,input().split())))
    
for i in range(1,n):
    li[i][0] += min(li[i-1][1],li[i-1][2])
    li[i][1] += min(li[i-1][0],li[i-1][2])                
    li[i][2] += min(li[i-1][1],li[i-1][0])                                   
print(min(li[-1]))
        
 cs
 

 

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 11053번 가장 긴 증가하는 부분 수열 / 파이썬(python)  (0) 2021.05.23
[백준] 1463번 1로 만들기 / 파이썬(python)  (0) 2021.05.23
[백준] 10816번 숫자 카드 2 / 파이썬(python)  (0) 2021.05.21
[백준] 1920번 수 찾기 / 파이썬(python)  (0) 2021.05.21
[백준] 1697번 숨바꼭질 / 파이썬(python)  (0) 2021.05.21
'코딩테스트/백준' Related Articles more
Comments