[BOJ / 백준] 1149 RGB거리 (S1^ / DP) - Python

링크

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

 

 

 

 

문제 해석

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

 

 

입력

첫 번째 줄 : n

  n : 집의 개수

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

 

 

출력

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

 

 

 

 

풀이 & 코드 해석

이 문제를 완탐으로 푼다면 매 집에 대해 3가지 경우의 수를 가지고, n이 최대 1000까지 있으므로, O(3^n)이 될 것입니다.

 

따라서 제한 시간 내에 풀기 위해서는 DP를 사용해야 합니다.

 

 

 

 

코드

import sys
sys.setrecursionlimit(10**8)

def recursive(idx, bef):
    global n
    if idx == n:
        return 0

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

    return dp[idx][bef]


n = int(input())

arr = []

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

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

print(recursive(0, -1))

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

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

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

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

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