8-2. DP(다이나믹동적계획법) 문제

1. 개미전사 문제

정답코드

#정수 N을 입력 받기
n = int(input())

#모든 식량 정보 입력 받기
array = list(map(int,input().split()))

#앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

#DP진행(바텀업)
d[0] = array[0]
d[1] = max(array[0],array[1])
for i in range(2,n):
    d[i] = max(d[i-1],d[i-2]+array[i])
print(d[n-1])

2. 1로 만들기 문제

정답 코드

x = int(input())

#앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001

#DP진행(바텀업)
for i in range(2,x+1):
    #현재의 수에서 1을 빼는 경우
    d[i] = d[i-1] + 1
    #현재의 수가 2로 나누어 떨어지는 경우
    if (i % 2 == 0):
        d[i] = min(d[i], d[i // 2]+1)
    #현재의 수가 3으로 나누어 떨어지는 경우
    if (i % 3 == 0):
        d[i] = min(d[i], d[i // 3]+1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if (i % 5 == 0):
        d[i] = min(d[i], d[i // 5] + 1)
print(d[x])