[BOJ / 백준] 17404 RGB거리 2 (G4 / DP) - Python

링크

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

 

 

 

 

문제 해석

집이 총 n개가 있음
집을 빨강, 초록, 파랑 중 하나로 칠해야 함
매번 칠할 떄 가격이 서로 다름
색상은 이전 집과 항상 달라야함

첫 번째 집과, n번째 집의 색상은 서로 달라야 함

 

 

입력
첫 번째 줄 : n
  n : 집의 개수

n개의 줄 : n번째 집을 칠할 때 드는 색상별 비용 

 

 

출력
모든 집을 칠하는 최소 값 구하기

 

 

 

 

풀이 & 코드 해석

어제 풀었던 RGB거리와 입력과 출력 양식이 정확히 동일한 문제입니다.

https://angelplayer.tistory.com/581

 

 

 

다만 위 문제와 차이점은 조건으로 첫 번째 집과, 마지막 집의 색상이 서로 달라야 한다는 점입니다.

 

이 문제를 해결하기 위해서 dp의 저장 조건에 첫 번째 집을 어떤 색을 칠했는지를 추가해 주었습니다.

 

 

 

 

코드

import sys
sys.setrecursionlimit(10**8)


def recursive(idx, bef, fir):
    global n
    if idx == n:
        if bef != fir:
            return 0
        else:
            return int(1e9)

    if dp[fir][idx][bef] == -1:
        ret = int(1e9)
        for i in range(3):
            if i != bef:
                ret = min(ret, recursive(idx + 1, i, fir) + arr[idx][i])
        dp[fir][idx][bef] = ret

    return dp[fir][idx][bef]


n = int(input())

arr = []

for _ in range(n):
    arr.append(list(map(int, input().split())))

dp = [[[-1] * 3 for _ in range(n)] for _ in range(3)]

ans = int(1e9)
for i in range(3):
    ans = min(ans, arr[0][i] + recursive(1, i, i))

print(ans)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java