백준_17404_RGB거리 2

문제

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

17404번: RGB거리 2

풀이

1) 첫번째 집에 사용할 페인트 색 고르기

첫번째 집과 마지막 집에 사용되는 페인트가 달라야 한다는 조건을 만족하기 위해 경우의 수를 나누어 계산하였다.

1. 첫번째 집에 빨간색 페인트를 사용한다.

두번째 집과 마지막 집의 빨간색 페인트가 선택되지 않기 위해서 충분히 큰 값을 넣는다.

첫번째 집의 초록색과 파란색 페인트가 선택되지 않기 위해서 충분히 큰 값을 넣는다.

2. 첫번째 집에 초록색 페인트를 사용한다.

두번째 집과 마지막 집의 초록색 페인트가 선택되지 않기 위해서 충분히 큰 값을 넣는다.

첫번째 집의 빨간색과 파란색 페인트가 선택되지 않기 위해서 충분히 큰 값을 넣는다.

3. 첫번째 집에 파란색 페인트를 사용한다.

두번째 집과 마지막 집의 파란색 페인트가 선택되지 않기 위해서 충분히 큰 값을 넣는다.

첫번째 집의 초록색과 빨간색 페인트가 선택되지 않기 위해서 충분히 큰 값을 넣는다.

2) 가장 적은 비용으로 페인트 칠하기

다이나믹 프로그래밍을 이용하여 해결하는 문제이며 이과정은 1149번과 동일하다. 

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

1149번: RGB거리

2021/02/05 - [코딩테스트] - 백준_1149_RGB거리

백준_1149_RGB거리

 

코드

# The first house is painted with red/green/blue paint.
# r, g, b = 0, 1, 2
# 비용은 1,000보다 작거나 같은 자연수
from sys import stdin
N = int(stdin.readline())
arr = [list(map(int, stdin.readline().split())) for i in range(N)]
ans = list()

for c in range(3) : # c=1:red / c=2:green / c=3:blue
    # 새로운 점수판을 생성하고, 첫번째, 두번째, 그리고 마지막 줄에 충분히 큰 값 넣기
    tmp = [[t for t in item] for item in arr]
    tmp[-1][c], tmp[1][c], tmp[0][c-1], tmp[0][c-2] = (1001,)*4

    # 순서대로 탐색하기
    for i in range(1, N) :
        for j in range(3) :
            tmp[i][j] += min(tmp[i-1][j-1], tmp[i-1][j-2])
    ans.append(min(tmp[-1]))
print(min(ans))