Python [AtoZ] Chapter 08. 다이나믹 프로그래밍

[ Table of Contents ]

다이나믹 프로그래밍

1. 피보나치 수열

2. 탑다운(=메모이제이션)

3. 보텀업(=DP의 전형적인 형태)

 

실전 문제

1. 1로 만들기

2. 개미 전사

3. 바닥 공사

4. 효율적인 화폐 구성

 

기출 문제

1. 금광

2. 정수 삼각형

3. 퇴사

4. 병사 배치하기

5. 못생긴 수

6. 편집 거리

[ Abstract ]

0. 계산 복잡도 : P-NP문제

1. DP란? 퀵정렬과는 다르며, 재귀 함수 말고 반복문으로 구현할 것

2. 탑다운(=메모이제이션) : 연속적이지 않은 경우 사전dict 자료형 사용 가능

3. 보텀업(=DP의 전형적인 형태) : DP테이블 사용

4. 피보나치 수열의 시간복잡도 : 재귀(O(2ᴺ)), DP(O(N))

 

다이나믹 프로그래밍

중복되는 연산을 줄이자

우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. (해결하기 어려운 문제에 대해서 깊게 다루는 분야로는 계산 복잡도 이론이 있다. 이 부분에 대해서 깊게 공부하기 위해서는 P-NP 문제를 다루는 계산 복잡도 이론에 대해 공부해보는 것을 추천한다.)

 

다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 이번 장에서 다루는 다이나믹 프로그래밍DP기법으로 동적 계획법이라고 표현하기도 한다. DP의 탑다운과 보텀업 2가지 방식과 특히 DP를 위해 자주 사용되는 메모이제이션 기법까지 소개하겠다.

(프로그래밍에서 다이나믹은 프로그램이 실행되는 도중에라는 의미이지만, 자료구조에서 동적 할당Dynamic Allocation은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이다.)

 

1. 피보나치 수열

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다.

1 1 2 3 5 8 13 21 34 55 59 ...

수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현한다. 점화식이란 인접한 항들 사이의 관계식을 의미하는데, 우리는 점화식을 이용해 현재의 항을 이전의 항에 대한 식으로 표현할 수 있다. 예를 들어 피보나치 수열의 점화식은 다음과 같이 표현할 수 있다.

  ᵃ ₙ ₊ ₂ = ᵃ ₙ ₊ ₁  + ᵃ ₙ , ᵃ ₁ = 1, ᵃ ₂ = 1

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문이다.

그렇다면 이 점화식에 따라서 실제로 피보나치 수를 구하는 과정을 어떻게 표현할 수 있을까? n번째 피보나치 수를 f(n)이라고 표현할 때 4번째 피보나치 수 f(4)를 구하려면 다음과 같이 함수 f를 반복해서 호출할 것이다. 그런데 f(2)와 f(1)은 항상 1이기 때문에 f(1)이나 f(2)를 만났을 때는 호출을 정지한다.

수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다. 예시를 소스코드로 바꾸면 다음과 같다.

#피보나치 수열 : 재귀 함수를 사용
def fibo(x):
    if x==1 or x==2:
        return 1
    return fibo(x-1) + fibo(x-2)
print(fibo(4)) #4

 

 

그런데 피보나치 수열의 소스코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 바로 f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 피보나치 수열의 정확한 시간 복잡도는 세타 표기법을 사용하여 θ(1.618...ᴺ)으로 표현할 수 있다. 하지만 일반적으로 빅오 표기법을 이용하여 O(2ᴺ)의 지수 시간이 소요된다고 표현한다. 예를 들어 N=30이면, 약 10억 가량의 연산을 수행해야 한다.

 

이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 이러한 문제는 DP를 사용하면 효율적으로 해결할 수 있다. 다만 항상 DP을 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

2. 탑다운(=메모이제이션)

피보나치 수열은 이러한 조건을 만족하는 대표 문제이다. 이 문제를 메모이제이션Memoization 기법을 사용해서 해결해보자. 메모이제이션은 DP을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱Caching이라고도 한다.

그렇다면 실제로 메모이제이션은 어떻게 구현될 수 있을까? 단순하다, 한 번 구한 정보를 리스트에 저장하는 것이다. DP을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다.

#피보나치 수열 : 탑다운 방식으로, 재귀 함수를 사용
d = [0] * 100 #한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화
def fibo(x):
    if x==1 or x==2:
        return 1
    if d[x] != 0: #이미 계산한 적이 있는 문제라면 그대로 반환
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2) #아직 계산하지 않은 문제라면 점화식에 따라 반환
    return d[x]
print(fibo(99)) #218922995834555169026

 

 

정리하자면 DP란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 사실 큰 문제를 작게 나누는 방법은 퀵 정렬에서도 소개된 적이 있다. 퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할아며 전체적으로 정렬이 될 수 있도록 한다. 이는 분할 정복Divide and Conquer 알고리즘으로 분류된다. DP와 분할 정복의 차이점은 DP는 문제들이 서로 영향을 미치고 있다는 점이다.

퀵 정렬을 예로 들면, 한 번 기준 원소Pivot가 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다. 반면에 DP는 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 이미 해결된 문제는 그 결과를 저장해 놓았다가 나중에 동일한 문제를 풀어야 할 때 이미 저장한 값을 반환한다. f(6)을 메모이제이션 기법을 이용하여 그려보면 6번째 피보나치 수를 호출할 때는 다음 그림처럼 색칠된 노드만 방문하게 된다.

처음 방식으로 호출했던 부분은 점선으로 노드를 표현했는데 사실상 호출되지 않는다고 이해하자. 왜냐하면 호출하더라도 따로 계산하지 않고 리스트에서 값을 가져오거나 바로 1을 반환하기 때문이다. 물론 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋기 때문이다.

그렇다면 DP을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 어떻게 될까? 바로 O(N)이다. 왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)를 푸는 데 사용되는 방식으로 이어지기 때문이다. 한 번 구한 결과는 다시 구해지지 않는다.

#피보나치 수열 : DP를 적용했을 때
d = [0] * 100
def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    if x==1 or x==2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]
fibo(6) #f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4) , 8

 

3. 보텀업(=DP의 전형적인 형태)

이처럼 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운Top-Down 방식이라고 말한다. 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업Bottom-Up 방식이라고 말한다. 피보나치 수열 문제를 보텀엄 방식으로 풀면 다음과 같다.

#피보나치 수열 : 보텀업 방식으로, 반복문 사용
d = [0]*100 #앞서 계산된 결과를 저장하기 위한 DP테이블 초기화
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n+1): #피보나치 함수 반복문으로 구현(보텀업 다이나믹 프로그래밍)
    d[i] = d[i-1] + d[i-2]
print(d[n]) #218922995834555169026

 

 

탑다운(메모이제이션) 방식은 하향식이라고도 하며, 보텀업 방식은 상향식이라고도 한다. DP의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용하는 표현이다. DP와 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미하므로, DP와는 별도의 개념이다.

또한 앞서 수열은 배열이나 리스트로 표현할 수 있다고 했는데, 메모이제이션은 때에 따라서 사전dict 자료형을 이용할 수도 있다. 사전 자료형은 수열처럼 연속적이지 않은 경우에 유용한데, 예를 들어 aᵣ 을 계산하고자 할 때 a₀ ~ aᵣ₋₁ 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우가 존재할 수 있다. 이럴 때에는 사전 자료형을 사용하는 게 더 효과적이다.

 

물론 3차원 리스트를 이용해야 하는 복잡한 난이도의 문제가 출제될 수도 있다. 이런 문제는 이어서 배울 Chap 09. 최단 경로의 플로이드 워셜 알고리즘에서 다룬다.

하지만 코딩 테스트에서의 DP 문제는 대체로 간다한 형태로 출제되므로, 이 책에서 다루는 문제 정도만 바르게 습득해도 DP 문제를 풀기에는 큰 어려움이 없을 것이다.

 

DP문제 풀이 순서

1. 주어진 문제가 DP 유형임을 파악하는 것이다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.

2. 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어다. 앞서 다루었던 피보나치 수열의 예제처럼 재귀 함수를 작성한 뒤에 나중에 메모이제이션 기법을 적용해 소스코드를 수정하는 것도 좋은 방법이다.

3. 또한 가능하다면 재귀 함수를 이용하는 탑다운 방식보다 보텀업 방식으로 구현하는 것을 권장한다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.

 

 

실전 문제

1. 1로 만들기

[난이도: 중하 / 풀이시간: 20분 / 시간제한: 1초 / 메모리제한: 128MB]

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

    a) X가 5로 나누어떨어지면, 5로 나눈다.

    b) X가 3으로 나누어떨어지면, 3으로 나눈다.

    c) X가 2로 나누어떨어지면, 2로 나눈다.

    d) X에서 1을 뺀다.

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

예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.

    1. 26 - 1 = 25 (a))

    2. 25 / 5 = 5 (a))

    3. 5 / 5 = 1 (c))

[입력 조건] 첫째 줄에 정수 X가 주어진다(1<=X<=30000)

[출력 조건] 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

 

문제 해설

문제에서 요구하는 내용을 점화식으로 표현해보자. 점화식 끝에 1을 더해주는 이유는 함수의 호출 횟수를 구해야 하기 때문이다.

따라서 이 점화식을 토대로 보텀업 DP로 소스코드를 작성해보자. 실제 코드로 구현할 때는 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해서만 점화식을 적용할 수 있다. 더불어 두 수 중에서 단순히 더 작은 수를 구하고자 할 때는 파이썬에서의 min( )함수를 이용하면 간단하다.

#1. 1로 만들기
'''풀이 과정
1.연필로 점화식 써보기 ai = min(ai-1, ai/2, ai/3, ai/5) + 1
2.dp[i] = dp[i-1] +1에서, 현재의 수에서 1을 빼는 경우 : 나누어 떨어지지 않는 경우는 무조건 1을 빼야 하기 때문에 횟수를 +1 해준다.
3.dp[i] = min(dp[i], dp[i//2]+1)에서 min()함수 안의 dp[i]는 위에서의 1을 빼는 경우이며, 이때 +1을 해주었으므로, 나누는 경우에도 각각 횟수를 +1 해주어야한다.
'''
x = int(input()) #26
dp = [0] * 30001 #앞서 계산된 결과 저장을 위한 DP테이블 초기화
for i in range(2, x+1): #다이나믹 프로그래밍 보텀업
    dp[i] = dp[i-1] +1 #1) 현재의 수에서 1을 빼는 경우 : 나누어 떨어지지 않는 경우는 무조건 1을 빼야 하기 때문에 횟수를 +1 해준다.
    if i % 2 == 0: #2) 현재의 수가 2로 나누어 떨어지는 경우
        dp[i] = min(dp[i], dp[i//2]+1) #이 행에서 min()함수 안의 dp[i]는 1을 빼는 경우고, 위에서 1을 빼는 경우 +1을 해주었으므로, 나누는 경우에도 각각 횟수를 +1 해주어야한다.
    if i % 3 == 0: #3) 현재의 수가 3으로 나누어 떨어지는 경우
        dp[i] = min(dp[i], dp[i//3]+1)
    if i % 5 == 0: #4) 현재의 수가 5로 나누어 떨어지는 경우
        dp[i] = min(dp[i], dp[i//5]+1)
print(dp[x]) #3 : dp[26]은 숫자 26의 1로 되기 위한 횟수, [0, 0, 1, 1, 2, 1, 2, 3, 3, 2, 2, 3, 3, 4, 4, 2, 3, 4, 3, 4, 3, 4, 4, 5, 4, 2, 3, ...]

 

 

2. 개미 전사

[난이도: 중 / 풀이시간: 20분 / 시간제한: 1초 / 메모리제한: 128MB]

개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.

{1, 3, 1, 5}

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량 창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

[입력 조건]

1. 첫째 줄에 식량 창고의 개수 N이 주어진다. (3<=N<=100)

2. 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0<=K<=1000)

[출력 조건]

첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오

#입력 예시
4
1 3 1 5
#출력 예시
8

 

 

문제 해설

이 문제 또한 그림으로 도식화한 뒤에 생각하면 어렵지 않다. 예를 들어 N이 4이고 차례대로 식량이 1, 3, 1, 5만큼 들어 있다고 가정하자. 그렇다면 식량을 선택할 수 있는 경우의 수는 8이다. 또한 7번째 경우에서 총 8만큼의 식량을 얻을 수 있기 때문에 정답은 8이다.

그럼 이 문제의 점화식은 어떻게 세울까? 처음 이 문제를 접했을 때는 문제 풀이를 위한 아이디어를 떠올리기 어려울 수 있지만 왼쪽부터 차례대로 식량창고를 턴다고 가정하면 어렵지 않게 점화식을 세울 수 있다. 왼쪽부터 차례대로 식량창고를 털지 안 털지를 결정하는 경우와 특정한 i번째 식량창고에 대해서 털지 안 털지의 여부를 결정할 때, 단 2가지 경우에 대해서만 확인하면 된다.

1. (i - 1) 번째 식량창고를 털기로 결정한 경우 현재(i번째)의 식량창고를 털 수 없다.

2. (i - 2) 번째 식량창고를 털기로 결정한 경우 현재(i번째)의 식량창고를 털 수 있다.

 

따라서 1과 2중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다.

여기서 알아둘 점은 i번째 식량창고에 대한 최적의 해를 구할 때 왼쪽부터 (i - 3)번째 이하의 식량창고에 대한 최적의 해에 대해서는 고려할 필요가 없다는 점이다. 예를 들어 dp[i-3]은 dp[i-1]과 dp[i-2]을 구하는 과정에서 이미 계산되었기 때문에, dp[i]의 값을 구할 때는 d[i-1]과 d[i-2]만 고려하면 된다. 따라서 i번째 식량창고에 있는 식량의 양이 ki라고 했을 때 점화식은 다음과 같다.

보텀업 방식의 풀이를 살펴보면 다음과 같다.

#2. 개미 전사
n = int(input()) #4
array = list(map(int, input().split())) #식량 정보 입력 받기 : 1 3 1 5
dp = [0] * 100 #앞서 계산된 결과 저장을 위한 DP테이블 초기화
dp[0] = array[0] #다이나믹 프로그래밍 보텀업
dp[1] = max(array[0], array[1]) #dp[1] = array[1]로 하면, 입력이 3 1 1 5 일때 1+5=6으로 최댓값 3+5=8에 미치지 못한다.
for i in range(2, n):
    dp[i] = max(dp[i-1], dp[i-2] + array[i]) #i-1번째 or i-2번째+i번째 중 큰값
print(dp[n-1]) #리스트 d[i]는 index 0부터 시작하므로 dp[n]이 아닌 dp[n-1]을 출력 : [1, 3, 3, 8, ... ]

 

 

3. 바닥 공사

[난이도: 중하 / 풀이시간: 20분 / 시간제한: 1초 / 메모리제한: 128MB]

2xN인 직사각형 형태의 얇은 바닥이 있다. 이 얇은 바닥을 1x2, 2x1, 2x2의 덮개를 이용해 채우고자 한다.

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2x3크기의 바닥을 채우는 경우의 수는 5가지이다.

[입력 조건] 첫째 줄에 N이 주어진다. (1<=N<=1000)

[출력 조건] 첫째 줄에 2xN 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

[입력 예시] 3

[출력 예시] 5

 

문제 해설

이 문제 또한 마찬가지로 다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다. DP문제에서 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가 있는 경우가 많다. 이 문제에서도 796,796으로 나눈 나머지를 출력하라고 하는데, 이는 단지 결괏값이 굉장히 커질 수 있기 때문에 그런 것이다. 따라서 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하도록 하면 된다.

또한 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.

1. 왼쪽부터 i - 1까지 길이가 덮개로 이미 채워져 있으면 2x1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다.

2. 왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면 1x2덮개 2개를 넣거나, 2x2 덮개 하나를 넣는 경우 2가지 경우가 존재한다. 참고로 2x1 덮개 2개를 넣는 경우를 고려하지 않는 이유는 1에서 이미 해당 경우가 고려되었기 때문이다.

 

또한 이 문제 역시 i번째 위치에 대한 최적의 해를 구할 때 왼쪽부터 (i - 3)번째 이하의 위치에 대한 최적의 해에 대해서는 고려할 필요가 없다. 왜냐하면 사용할 수 있는 덮개의 형태가 최대 2x2 크기의 직사각형 형태이기 때문이다. 다시 말해 바닥을 채울 수 있는 형태는 위에서 언급한 경우밖에 없다. 따라서 다음과 같이 점화식을 세울 수 있다.

왼쪽부터 N - 2까지 길이가 덮개로 이미 채워져 있는 경우 덮개를 채우는 방법은 2가지 경우가 있다. 이 두 방법은 서로 다른 것이므로, 결과적으로 위와 같은 점화식이 된다.

#3. 바닥 공사
n = int(input()) #3
dp = [0] * 1001 #앞서 계산된 결과 저장을 위한 DP테이블 초기화
dp[1] = 1 #다이나믹 프로그래밍 보텀업, 1x2타일 1개 = 총 '1'가지 경우
dp[2] = 3 #1x2타일 2개, 2x2타일 1개, 2x1타일 2개 = 총 '3'가지 경우
for i in range(3, n+1):
    dp[i] = (dp[i-1] + dp[i-2]*2) %796796 #i-2번째는, 1x2타일 2개 or 2x2타일 1개 = 총 '2'가지 경우이므로 'x2'를 한다.
print(dp[n]) #dp[i]를 dp[1]부터 채웠으므로 dp[n]을 출력하면 된다. : 5

 

 

4. 효율적인 화폐 구성

관련 문제 : 동전2(https://www.acmicpc.net/problem/2294), 동전1(https://www.acmicpc.net/problem/2293)

[난이도: 중 / 풀이시간: 30분 / 시간제한: 1초 / 메모리제한: 128MB]

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

[입력 조건]

1. 첫째 줄에 N, M이 주어진다. (1<=N<=100, 1<=M<=10000)

2. 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10000보다 작거나 같은 자연수이다.

[출력 조건]

1. 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.

2. 불가능할 때는 -1을 출력한다.

#입력 예시
2 15
2
3
#출력 예시
5

 

 

문제 해설

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

이번 문제는 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다. 금액 i를 만들 수 있는 최소한의 화폐 개수를 ai, 화페 단위를 k라고 했을 때 다음과 같은 점화식을 작성할 수 있다. ai-k는 금액 (i - k)를 만들 수 있는 최소한의 화폐 개수를 의미한다.

이 점화식을 모든 화폐 단위에 대하여 차례대로 적용하면 된다. 실제로 문제를 풀기 위해서는 가장 먼저 K의 크기만큼 리스트를 할당한다. 이후 각 인덱스를 금액으로 고려하여 메모이제이션을 진행한다. 예를 들어 N=3, K=7이고, 각 화폐의 단위가 2, 3, 5인 경우를 생각해보자.

1. 초기화 : 각 인덱스에 해당하는 값으로 10001을 설정한다. 10001은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미이다. M의 최대 크기가 10000이므로 불가능한 수로 10001이라는 값을 설정했으며, 이보다 더 큰 수여도 상관 없다. 또한 0원의 경우, 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 값으로 0을 설정한다. 따라서 초기 리스트의 값은 다음과 같다.

인덱스	0	1	2	3	4	5	6	7
값	0	10001	10001	10001	10001	10001	10001	10001

 

2. 화폐 단위 : 2, 3, 5 가장 먼저 첫 번째 화폐 단위인 2부터 확인한다. 앞서 언급한 점화식에 따라 다음과 같이 리스트가 갱신된다. 예를 들어 인덱스 2의 경우 1이라는 값을 가지는데, 이는 2원짜리 화폐 하나를 이용하여 2원을 만들 수 있다는 의미이다. 인덱스 4의 경우 2라는 값을 가지는데, 이는 2원짜리 화폐를 2개 이용하여 (2+2) = 4원을 만들 수 있다는 의미이다. 몇 인덱스의 경우 10001의 값을 그대로 가지는데, 이는 2원짜리 화폐를 가지고 구성할 수 없는 금액이기 때문이다. 예를 들어 인덱스 3의 경우 인덱스 1의 값이 10001이므로 마찬가지로 10001의 값을 가진다.

인덱스	0	1	2	3	4	5	6	7
값	0	10001	1	10001	2	10001	3	10001

 

3. 화폐 단위 : 2, 3, 5 이어서 화폐 단위 3을 확인한다. 앞서 언급한 점화식에 따라서 값을 도출하면 다음과 같이 리스트가 갱신된다. 예를 들어, 인덱스 5의 경우 2라는 값을 가지는데, 2원짜리 화폐 1개, 3원짜리 화폐 1개로 (2+3) = 5원을 만들 수 있다는 의미가 된다.

인덱스	0	1	2	3	4	5	6	7
값	0	10001	1	1	2	2	2 (갱신)	3

 

4. 화폐 단위 : 2, 3, 5 이어서 화폐 단위 5를 확인한다. 2원짜리 화폐 1개, 5원짜리 화폐 1개로 (2+5) = 7원을 만들 수 있다는 의미가 된다. 원래 이전 단계에서 a7의 값은 3이었는데, 이는 (2+2+3) = 7원으로 3개의 화폐를 사용했을 때를 나타낸 것이다. 다만, 현재 단계에서 (2+5) = 7원을 만들면 화폐를 2개만 사용해도 되므로, 더 작은 값으로 갱신된다.

인덱스	0	1	2	3	4	5	6	7
값	0	10001	1	1	2	1 (갱신)	2	2 (갱신)

 

결과적으로 7원을 만들기 위한 최소 화폐 개수는 2개이다. 따라서 앞서 언급한 점화식을 그대로 소스코드로 옮기면 다음과 같다. 또한 아래 코드에서 d[ j - array[ i ] ]가 10001인지 검사하는 부분은 사실 없어도 되는 코드인데, d[ j - array[ i ] ] 가 10001의 값을 가지더라도 min(d[ j ], d[ j - array[ i ] ] + 1)은 항상 d[ j ]의 값을 반환하기 때문이다. 다만, 이해를 돕기 위해 코드에는 그대로 넣어주었다.

#4. 효율적인 화폐 구성
n, m = map(int, input().split()) #화폐종류 n가지, 구할 값 m
array = [] #n개의 화폐 단위 정보 입력 받기
for i in range(n):
    array.append(int(input()))
dp = [10001] * (m+1) #한 번 계산된 결과를 저장하기 위한 DP테이블 초기화
dp[0] = 0 #다이나믹 프로그래밍 보텀업
for i in range(n):
    for j in range(array[i], m+1): #j는 array[i]값(ex:2)부터 dp테이블 마지막인 m+1까지
        if dp[j - array[i]] != 10001: #금액(i-k)원을 만드는 방법이 존재하는 경우인데, 없어도 되는 코드이다.
        #d[j - array[i]] 가 10001의 값을 가지더라도 min(d[j], d[j - array[i]] + 1)은 항상 d[j]의 값을 반환하기 때문
            dp[j] = min(dp[j], dp[j - array[i]]+1) #j=2이면 dp[2]=1이고, j=4이면 dp[4]=dp[4-array[0]]+1=dp[4-2]+1=dp[2]+1=1+1=2 ...
if dp[m] == 10001: #최종적으로 m원을 만드는 방법이 있는 경우
    print(-1)
else:
    print(dp[m])

 

 

기출 문제

1. 금광

2. 정수 삼각형

3. 퇴사

4. 병사 배치하기

5. 못생긴 수

6. 편집 거리

 

 

이 글은 주인장의 자습 목적을 위해 <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 99.99% 참고하여 만들었다.