알고리즘

<백 준> 1149번 파이썬 알고리즘

changha. 2021. 1. 13. 22:11

-다이나믹 알고리즘

n = int(input()) # 행
m = 3 # 열
d = []
# 그래프 만들기
for i in range(n):
    d.append(list(map(int,input().split())))

for i in range(1, n):
    for j in range(m):
        if j == 0:
            d[i][j] = d[i][j] + min(d[i - 1][j + 1], d[i - 1][j + 2])
        if j == 1:
            d[i][j] = d[i][j] + min(d[i - 1][j - 1], d[i - 1][j + 1])
        if j == 2:
            d[i][j] = d[i][j] + min(d[i - 1][j - 1], d[i - 1][j - 2])

print(min(d[n-1][0],d[n-1][1],d[n-1][2]))

 

 

 

동빈나 DF 강의에서의 예제와 접근 방식이 비슷해서 비교적 쉽게 풀었다

www.acmicpc.net/problem/1149 

 

1149번: RGB거리

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

www.acmicpc.net