[알고리즘] 백준 1149 - RGB거리

문제

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

 

풀이

9달 전에도 풀었던 문제여서 그런지 그냥 보자마자 현재 집이 빨강이면 이전집 초록 블루 비용에 현재 빨강 비용을 더했을 때 더 적은 값을 저장해두고 마지막 배열에서 min인 값을 찾으면 되겠다...고 생각했다.

 

정답 코드

n = int(input())

minr,ming,minb = 0,0,0
for i in range(n):
    r,g,b = map(int,input().split())
    if i==0:
        minr=r
        ming=g
        minb=b
    else:
        new_minr = min(ming+r,minb+r)
        new_ming = min(minb+g,minr+g)
        new_minb = min(ming+b,minr+b)

        minr = new_minr
        minb = new_minb
        ming = new_ming

print(min(minr,minb,ming))

 

이렇게 짜긴했는데 사실 일반 DP처럼 2차원 배열을 저장해두고 풀어도 된다. (이게 더 정석(?)이려나)

내가 9달 전에 풀었던 풀이가 비슷한 맥락에서 풀었던 답이다.

n=int(input())
cost=[]
for i in range(n):
    r=list(map(int,input().split()))
    cost.append(r)

arr=[[0 for _ in range(3)] for _ in range(n+1)]
arr[1][0]=cost[0][0]
arr[1][1]=cost[0][1]
arr[1][2]=cost[0][2]

for i in range(2,n+1):
    arr[i][0]=cost[i-1][0]+min(arr[i-1][1],arr[i-1][2])
    arr[i][1]=cost[i-1][1]+min(arr[i-1][0],arr[i-1][2])
    arr[i][2]=cost[i-1][2]+min(arr[i-1][1],arr[i-1][0])

print(min(arr[n]))