Dynamic Programming 적용문제

1로 만들기

정수가 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음 4가지 이다.

• X가 5로 나누어 떨어지면, 5로 나눈다.
• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

문제

• 첫째 줄에 정수 X가 주어진다.(1 <= X <= 30,000)

접근 방법

다이나믹 프로그래밍 문제이다. 그림으로 이해하면 좋은데, 다음은 X=6일 때, 함수가 호출되는 과정이다.

해당 내용을 점화식으로 표현하면 다음 식과 같고, 점화식 끝에 1을 더해주는 이유는 함수의 호출 횟수를 구해야 하기 때문이다. 파이썬의 min()함수를 사용하면 편하다.
\(a_i = min(a_{i-1},a_{i/2},a_{i/3},a_{i/5}) + 1\)

코드

# 정수 X를 입력 받기
x = int(input())

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
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)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

26
3

개미전사

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 여러 개의 식량창고는 일직선으로 이어져 있다. 각 식량 창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 1, 3, 1, 5 의 식량창고가 있다면 개미 전사는 두 번째, 네 번째 식량창고를 털여야 최댓값인 8개의 식량을 빼앗을 수 있다.

문제

• 첫째 줄에 식량창고의 개수 N이 주어진다. (3 <= N <= 100)
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 <= K <= 1,000)
• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

접근방법

왼쪽 부터 차례대로 식량창고를 턴다고 가정하고 점화식을 세우자.

• i-1 번째 식량창고를 털면 i번째 식량창고를 털 수 없다.
• i-2 번째 식량창고를 털면 i번째 식량창고를 털 수 있다.
• i-3 번째 식량창고는 고려할 필요가 없다. 한칸 이상 떨어진 식량창고 항상 털 수 있기 때문이다.
  따라서 i번째 식량창고에 있는 식량의 양이 $k_i$라고 했을 때 점화식은 아래와 같다.
  $a_i = max(a_{i-1},a_{i-2}+k_i)$

코드(바텀업 방식)

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

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
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])

4
1 3 1 5
8

바닥 공사

다음과 같은 바닥을 덮개로 덮으려고 한다. 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성해라.

문제

• 첫째 줄에 N이 주어진다. (1 <= N <= 1,000)
• 첫째 줄에 2 x N 크기의 바닥을 채우는 방법의 수를 796,696으로 나눈 나머지를 출력한다.

접근방법

이 문제도 다이나믹 프로그래밍의 기초 예제인 타일링 문제 유형이다. 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.

• 왼쪽부터 i-1까지 길이가 덮개로 이미 채워져 있으면 2x1 덮개를 채우는 하나의 경우밖에 존재하지 않는다.
• 왼쪽부터 i-2까지 길이가 덮개로 이미 채워져 있으면 1x2 덮개 2개를 넣는 경우, 혹은 2x2의 덮개 하나를 넣는 경우로 2가지 경구가 존재한다.
  이 문제도 왼쪽부터 N-2 미만의 길이에 대해서는 고려할 필요가 없다. 왜냐하면 사용할 수 있는 덮개의 형태가 최대 2x2의 직사각형 형태이기 때문이다.
  $a_i = a_{i-1}+a_{i-2} * 2$

코드

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

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796

# 계산된 결과 출력
print(d[n])

3
5

효율적인 화폐 구성

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

문제

• 첫째 줄에 N,M이 주어진다. (1 <= N <= 100, 1 <= M <= 10,000)
• 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.
• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.
• 불가능할 때는 -1을 출력한다.

접근방법

이 문제는 그리디방법으로 해결한 거스름돈 문제와 동일하다. 단지 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점만 다르다. 그렇기 때문에 그리디 알고리즘 처럼 매번 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없고 다이나믹 프로그래밍을 이용해야 한다.

이 문제는 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다. 금액 i를 만들 수 있는 최소한의 화폐 개수를 $a_i$, 화폐의 단위를 $k$라고 했을 때 점화식은 아래와 같고, $a_{i-k}$는 금액 $(i-k)$를 만들 수 있는 최소한의 화폐 개수이다.

• $a_{i-k}$ 를 만드는 방법이 존재하는 경우, $a_{i} = min(a_{i},a_{i-k}+1)$
• $a_{i-k}$ 를 만드는 방법이 존재하지 않는 경우, $a_{i} = 10,0001$
  

코드

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

2 15
2
3
5