[BaekJoon] 백준 17404번 : RGB거리 2

17404번 : RGB거리 2

[BaekJoon] 백준 1149번 : RGB거리 에서 원형 조건이 추가 된 문제이다.

풀이 방법은 첫 번째 집을 빨간색, 초록색, 파란색으로 칠하는 경우를 나누어 세 번 계산하면 된다.

첫 번째 집을 빨간색으로 칠한다고 가정하는 경우 초록색, 파란색을 칠하는 가격은 무한대로 설정한 뒤 RGB 문제와 똑같이 계산한다.

마지막 계산 후 원형 조건을 충족시키기 위해 마지막 행 빨간색 열은 다시 무한대로 값을 바꾼다.

이렇게 세 번 반복하고 세 가지 값 중 최솟값을 출력하면 된다.

---

import sys
from copy import deepcopy


def painting(paint):
    arr = deepcopy(info)
    if paint == 0:
        arr[0][1] = arr[0][2] = float('inf')
    if paint == 1:
        arr[0][0] = arr[0][2] = float('inf')
    if paint == 2:
        arr[0][0] = arr[0][1] = float('inf')

    for i in range(1, N):
        for j in range(3):
            if j == 0:
                arr[i][j] += min(arr[i - 1][j + 1], arr[i - 1][j + 2])
            if j == 1:
                arr[i][j] += min(arr[i - 1][j - 1], arr[i - 1][j + 1])
            if j == 2:
                arr[i][j] += min(arr[i - 1][j - 2], arr[i - 1][j - 1])
    arr[N - 1][paint] = float('inf')

    return min(arr[N - 1])


def solution():
    answer = float('inf')
    for i in range(3):
        answer = min(answer, painting(i))

    return answer


if __name__ == "__main__":
    N = int(input())
    info = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(N)]

    print(solution())