[백준] 1149. RGB거리 - python3

1149. RGB거리

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

1149번: RGB거리

 

 

내 풀이 - 실패

코드

from sys import stdin
import sys

sys.setrecursionlimit(10**6)

N = int(stdin.readline())
costs = []
answer = float('inf')

for _ in range(N):
    R, G, B = map(int, stdin.readline().split())
    costs.append([R, G, B])

def func(costs, now, prev, ans):
    global answer
    
    if answer < ans:
        return
    if now == len(costs):
        answer = min(answer, ans)
        return
    
    if prev == 0:
        func(costs, now+1, -1, ans+costs[now][0])
        func(costs, now+1, 1, ans+costs[now][2])
    else:
        func(costs, now+1, 0, ans+costs[now][1])
        func(costs, now+1, -prev, ans+costs[now][1-prev])
        
        
for i in range(3):
    func(costs, 1, i-1, costs[0][i])

print(answer)

 

완전탐색으로 풀었더니 역시나 시간초과가 났다.

맨 처음 시작만 3 가지 색 모두로 함수 돌리고

나머지는 자신을 제외한 나머지 2 개 색의 모든 경우를 확인하도록 했다.

 

백퍼 DP 를 써야하는 것 같다.

 

 

내 풀이 - 성공

from sys import stdin

N = int(stdin.readline())
costs = []

for _ in range(N):
    R, G, B = map(int, stdin.readline().split())
    costs.append([R, G, B])

dp = costs[0]

for i in range(1, N):
    now = [0]*3
    for j in range(3):
        if j == 0:
            c = min(dp[1], dp[2])
            now[j] = costs[i][j] + c
        elif j == 1:
            c = min(dp[0], dp[2])
            now[j] = costs[i][j] + c
        else:
            c = min(dp[0], dp[1])
            now[j] = costs[i][j] + c
    dp = now

answer = min(dp)

print(answer)

 

DP 를 만들어서 누적 최솟값을 저장해줬다.

 

맨 처음 값은 1 번 집의 RGB 값으로 세팅하고

나머지는 for 문을 돌면서 지금 비용에 "칠할 수 있는 이전 값 중 최소"를 더한 값으로 DP 값을 갱신해줬다.

R 을 선택할 경우) R 비용 + DP 값(G, B 중 최솟값)

 

그렇게 누적으로 더하다보면 마지막 DP 값 중 최솟값이 최소비용이 된다.

 

 

 

참고)

DP 배열을 만들지 않고 costs 만으로 하는 방법

 

for i in range(1, N):
    costs[i][0] = min(costs[i-1][1], costs[i-1][2]) + costs[i][0]
    costs[i][1] = min(costs[i-1][0], costs[i-1][2]) + costs[i][1]
    costs[i][2] = min(costs[i-1][0], costs[i-1][1]) + costs[i][2]

print(min(costs[N-1]))

 

더 간단하게 할 수 있다.