백준 1149(RGB) - python

접근

브루트포스로 모든 경우 탐색을 해서 최소 비용을 알아내야겠다.

dfs로 탐색해서 최소값을 업데이트하고 최소값을 비교해가면서 최소값보다 합이 커지면 처음 단계로 돌아가야겠다.

 

나의 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())
M = [list(map(int,input().split())) for _ in range(n)]

minvalue = sys.maxsize
def dfs(cnt,value,p):
    global minvalue
    if value >= minvalue:
        return
    if cnt == n:
        minvalue = min(value,minvalue)
    else:
        for i in range(3):
            if p != i:
                dfs(cnt+1,value+M[cnt][i],i)

dfs(0,0,-1)
print(minvalue)

이렇게 푸니 바로 시간초과가 발생했다. 더빠른 방법으로 다이나믹 프로그래밍으로 접근할 생각을 했다.

30 20 10

20 10 30

40 20 10

20 10 30

이렇게 색을 칠하는 가격이 나온다면

[30]          [20]        [10]

[20+10] [10+10] [30+20]

[40+20] [20+30] [10+20]

...

이렇게 누적해서 각 열마다 최대의 경우의 수를 저장해나간다.

 

코드 보완

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())
M = [list(map(int,input().split())) for _ in range(n)]
minM = [[0]*3 for _ in range(n)]
minM[0][0] = M[0][0]
minM[0][1] = M[0][1]
minM[0][2] = M[0][2]
for i in range(1,n):
    for j in range(3):
        if j == 0:
            minM[i][0] = M[i][0]+min(minM[i-1][1],minM[i-1][2])
        elif j == 1:
            minM[i][1] = M[i][1]+min(minM[i-1][0],minM[i-1][2])
        else:
            minM[i][2] = M[i][2]+min(minM[i-1][1],minM[i-1][0])

print(min(minM[n-1]))