[백준] [Python] RGB거리 - DP

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

1149번: RGB거리

 

 

 

Python

i번째에

Red를 택했다면,

Green을 택했다면,

Blue를 택했다면,    이란 구조로 한 단계마다 전체 과정이 누적되어 진행할 수 있다

import sys
input = sys.stdin.readline

n = int(input())
rgbList = list(map(int,input().split()))

for _ in range(n-1):
    rgb = list(map(int,input().split()))
    prev = rgbList.copy()
    for i in range(3):
        rgbList[i] = rgb[i] + min(prev[i-1], prev[i-2])
    #rgbList[0] = rgb[0] + min(prev[2], prev[1])
    #rgbList[1] = rgb[1] + min(prev[0], prev[2])
    #rgbList[2] = rgb[2] + min(prev[1], prev[0])
    

print(min(rgbList))          

 

 

실패

4
1 1 1
1 1 1
2 1 2
9 1 9

이 예시의 답은 5이지만

아래 코드에서는 12가 나온다

 

DP 리스트의 기준을 시작점을 Red, Green, Blue 중 어느 것을 택했는지에 따라서 결정했기에

다음 번째를 골라야 할 때 이전 것을 알아내야 한다는 단점이 있었다.

import sys
input = sys.stdin.readline

n = int(input())
r,g,b = map(int,input().split())

dpRGB = [[[r,0]], [[g,1]], [[b,2]]]
x, xidx = 0, 0

for _ in range(n-1):
    rgb = list(map(int,input().split()))
    
    for i in range(3):
        prev = dpRGB[i][-1][1]
        
        if prev == "a": #all
        	# 이전 값이 같다면 그 다음은 어디든 다 가능해진다
            x = min(rgb)
            xidx = rgb.index(x)   
        else:
            if rgb[prev-1] == rgb[prev-2]:
                x = rgb[prev-1] 
                xidx = "a"
            else:
                x = min(rgb[prev-1], rgb[prev-2])
                xidx = rgb.index(x)
                
        dpRGB[i].append([dpRGB[i][-1][0]+x, xidx])

print(min([dpRGB[i][-1][0] for i in range(3)]))    

 

 

+) 비슷한 문제

https://wakaranaiyo.tistory.com/260

[백준][Python] 2096번 내려가기 - DP