백준 1149(RGB) - python
2023. 9. 26. 19:01ㆍ알고리즘(python)/DP
접근
브루트포스로 모든 경우 탐색을 해서 최소 비용을 알아내야겠다.
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]))
'알고리즘(python) > DP' 카테고리의 다른 글
백준 11053(가장 긴 증가하는 부분 수열) - python (0) | 2023.10.08 |
---|---|
백준9251(LCS) - python (0) | 2023.10.07 |
백준 1932(정수 삼각형) - python (0) | 2023.10.05 |