[Baekjoon]백준 1149 RBG거리(실버 1) - Python

문제설명

예제

문제를 살펴보면 각 줄에서 최솟값을 찾아서 출력하는 것이 아니라 바로 옆칸과는 색깔이 겹치면 안된다는 조건이 있다

이전 문제에서 부분합을 구하는 알고리즘인 카데인-알고리즘을 배웠기 때문에 어렵지 않게 문제를 해결 가능하다

각 줄을 내려가면서 카데인 알고리즘을 통해 최솟값으로 값을 변경하면 되기 때문이다

 

일단 각 색깔의 비용을 for문을 통해 입력받아주고, 부분합을 구하면 된다

for _ in range(N):
    color.append(list(map(int, input().split())))

서로 옆칸의 색깔과는 겹치면 안되기 때문에 빨강색은 초록색, 파란색을 더한 값 중에서 최솟값을 구해야한다

# calculate Prefix Sum
for i in range(1, N):
    color[i][0] += min(color[i-1][1], color[i-1][2])
    color[i][1] += min(color[i-1][0], color[i-1][2])
    color[i][2] += min(color[i-1][0], color[i-1][1])

이러한 방식을 사용하면 카데인 알고리즘을 통해 간단히 해결할 수 있다

마지막줄에서 min함수를 통해 color[N-1]에 위치한 값들 중에서 최솟값을 출력하면 된다

카데인 알고리즘은 이전 글에서 다루었으니 여기서는 생략하도록 하겠다