[TAVE/이코테] ch08 다이나믹 프로그래밍 | 실전 문제

참고자료: 이것이 코딩테스트다

실전 - 1로 만들기

x = int(input())

d = [0] * 30001

for i in range(2, x + 1):
    d[i] = d[i - 1] + 1

    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)

    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)

    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

👉🏻d의 각 자리에 연산을 얼마나 했는지 저장해주는 것이 point다.

• 숫자를 for문 돌리면서 각 연산을 모두 시도해준다. if-else문이 아닌 3개의 if문을 쓴 건 모든 연산을 다 가능한지 확인하기 위함이다.
• d[i]의 이전값이 d[x-1]에 +1을 한다. 여기서 d에 저장하는 값은 연산횟수이므로 d[x-1]에 비해 연산을 한 번 더 한 d[x]에 +1을 하는 것이다.
• 다음으로 2로 나누어지는지 확인을 한다. 그리고 d[i]를 d[i//2]+1과 비교해 더 작은 값을 저장한다. d[i//2]에 +1을 하는 이유는 연산을 한 번 더 하기 때문이다. 최소 연산을 구해야 하기 때문에 최솟값을 저장한다.
• 3과 5로 나눌 때도 마찬가지이다.

 

실전 - 개미전사

storage_count = int(input())
storage = list(map(int, input().split()))

d = [0] * 100
d[0] = storage[0]
d[1] = max(storage[0], storage[1])

for i in range(2, storage_count):
    d[i] = max(d[i -1], d[i - 2] + storage[i])

print(d[storage_count -1])

• 창고를 한 칸씩 털 수 있다는 것은 짝수는 짝수끼리 홀수는 홀수끼리 비교해야하므로 d[0]과 d[1]에는 먼저 값을 넣어준다. -> 얘는 최 max값?
• d[i - 1]과 d[i -2] + storage[i]를 비교한다. 현재 창고를 턴다면 바로 이전 창고를 털 수 없기 때문에 둘을 비교해 최댓값을 d[i]에 저장해준다.

 

실전 - 바닥 공사

N = int(input())

d = [0] * 1001

d[1] = 1
d[2] = 3

for i in range(3, N):
    d[i] = (d[i - 1] + (d[i - 2] * 2)) % 796796

print(d[n])

 

실전 - 효율적인 화폐 구성

N, M = map(int, input().split())
array = []
for _ in range(N):
    array.append(input())

d = [10001] * (M + 1)

d[0] = 0
for i in range(N):
    for j in range(array[i], M + 1):
        if d[j - array[i]] != 10001:
            d[j] = min(d[j], d[j - array[i]] + 1)

if d[M] == 10001:
    print(-1)
else:
    print(d[M])