DP(Dynamic Programming)

정보올림피아드 알고리즘 자료집 No.13
난이도 ★★★☆☆

1 , 5 , 10 , 40 , 50 (원) 의 동전이 들어있는 자판기가 있다.
투입금액과, 물건금액을 입력하면, 위의 동전을 사용하여(모두 사용할 필요는 없다) 잔돈을 거슬러주는 프로그램을 작성하라.
구매자의 호주머니를 가볍게 해 주기 위하여 거슬러 주는 동전의 개수가 최소가 되어야 한다.

프로그램의 이름은 “coin"으로 한다.

입력 형식
입력 파일 이름은 “Input.txt"로 한다.
한 줄에 자동판매기에 넣은 지폐의 금액 W(0≤W≤100000)과 물건의 가격이 주어진다.

출력 형식
출력 파일 이름은 "Output.txt"로 한다.
각 줄에 각 동전별(50 40 10 5 1) 순서대로 사용한 동전의 개수를 출력한다.

입력의 예(1) - (Input.txt)
1000 863

출력의 예(1) - (Output.txt)
1
2
0
1
2

입력의 예(2) - (Input.txt)
100000 753

출력의 예(2) - (Output.txt)
1984
1
0
1
2

문제의 배경 및 관련 알고리즘

1. 그리드 알고리즘(Greedy, 욕심쟁이)
- 현재 상황에서 가장 좋아 보이는 것을 택하는 것이다. 그 이유는 현재 상황에서 가장 좋은 것을 선택했을 때 전체적인 상황이 가장 좋게 되도록 하기 위함이다.
상당부분 그리드 알고리즘으로 최적 해를 구할 수 있다. 그러나 모든 경우에 그리드 방법이 통하는 것은 아니다. 또한 대부분의 휴리스틱의 문제의 경우 그리드 알고리즘을 사용하면 최적 해에 근접한 결과를 얻을 수 있다. 그리드 알고리즘을 사용하는 문제의 유형으로 동전교환문제, 냅색문제 등이 있다.

2. 다이나믹(Dynamic)
- 모든 해를 다 찾아보되 한번 찾아본 해는 다시 찾지 않고 찾아진 결과를 가져다 보는 것. 소스가 간결한 편이며 그리드 알고리즘과 함께 가장 많이 쓰이는 풀이법 중 하나임.

3. 백트래킹(Backtracking, 퇴각검색)
- 주어진 조건을 만족하는 최적해 또는 해들의 집합을 찾는 문제에 주로 사용하는 방법으로 주어진 상태공간을 트리로 구성해서 깊이우선 탐색(DFS) 등을 이용하여 상태공간을 체계적으로 탐색하는 방법이다.
이는 그리드 알고리즘 등으로는 효율적으로 해결할 수 없는 문제에 적용하여 최적해에 접근할 수 있으나 지수 시간의 복잡도를 갖는 단점이 있다. 이를 극복하기 위해 트리의 각 노드에서 더 이상 탐색이 필요 없는 부분을 제외시킴으로서 탐색할 범위를 줄이는 방법이 있다.

문제의 접근

일반적으로 우리 일상에서 사용하고 있는 동전을 이용한 동전교환 문제는 그리드(Greedy) 알고리즘을 이용하여 최소 동전의 개수를 바꿀 수 있다. 만약 동전이 아래와 같이 1원, 5원, 10원, 50원의 동전을 사용하고 있을 때,

1 5 10 50

137원의 동전을 거슬러 줘야 한다면 사용하고 있는 1원, 5원, 10원, 50원의 동전 중 금액이 제일 큰 50원을 거슬러 줄 수 없을 때까지 거슬러 준 다음 10원짜리 동전을 같은 방법으로 거슬러 주고 다음은 5원짜리 1원짜리 동전 순으로 거슬러 주면 된다.
137원에서 50원짜리는 최대 2개를 거슬러 줄 수 있고 이때 37원이 남는다. 50 50 37원에서 10원짜리는 최대 3개를 거슬러 줄 수 있고 이때 7원이 남는다.
10 10 10 7원에서 5원짜리는 최대 1개를 거슬러 줄 수 있고 이때 2원이 남는다.
5 2원에서 1원짜리로 2개를 거슬러 주면 잔액은 0원이 된다.
1 1 따라서137원을 최소동전의 개수로 거슬러 주기위한 동전의 개수는 50원 2개, 10원 3개, 5원 1개, 1원 2개로 총 8개가 된다.
그리드 알고리즘을 사용하기 위해서는 큰 액수의 동전은 작은 액수의 동전의 “배수” 관계일 때에만 가능하다. 5원짜리가 2개 있다면 합이 10원으로 5원짜리 2개보다 10원짜리 한개가 더 최소한의 동전 교환 개수가 되기 때문에 서로 배수 범위보다 큰 동전의 개수를 갖지는 못한다.
즉, 어느 동전을 가지고 있을 때 그 합이 한 단계 위의 동전만큼 된다면 그것은 최소한의 동전 개수라고 할 수 없다.
그러나 주어진 문제처럼 40원짜리 동전을 새로 만들어 냈다면 새로 만든 40원은 1원, 5원,10원과의 배수관계는 성립하지만 50원과의 배수관계는 성립하지 않기 때문에 그리드 방법으로 해를 구하면 항상 최적해가 나오는 것은 아니다.
만약 137원을 동전으로 바꿀 때 그리드 알고리즘을 이용하면 50원짜리 2개, 40원짜리 0개, 10원짜리 3개, 5원짜리 1개, 1원짜리 2개로 총 8개의 동전이 필요하다. 그러나 달리 생각을 하면 50원짜리 1개, 40원짜리 2개, 10원짜리 0개, 5원짜리 1개, 1원짜리 2개로 총 6개가 필요함을 볼 수 있다.
이제 동전을 최소 개수로 거슬러줄 때 항상 최적 해를 구하기 위해 다이나믹(Dynamic)방법을 생각해 보자. 장황하다.....;
다이나믹 방법은 동전을 거슬러줄 모든 금액을 다 살펴보아야 하지만 한번 살펴본 같은 금액을 찾기 위해 다시 반복해서 계산할 필요가 없는 특징이 있다.
예를 들어 1원짜리 동전과 5원짜리 동전이 있다고 할 때 11원을 만들려고 한다면 11원은 “6원”에 5원짜리 동전 1개를 추가해서 만들거나 아니면 “6원”에 1원짜리 동전 5개를 추가 해서 만들 수 있다. 그렇다면 6원을 만들기 위해서는 최소한의 동전이 몇 개 필요한지 알아보자. 6원은 1원짜리 동전 6개나 1원짜리 동전 1개와 5원짜리 동전 1개로 만들 수 있는데 “1원+5원”으로 6원을 만드는 것이 최적이라는 것을 알 수 있다.
이 최적해인 6원(1원+5원)을 이용해 11원의 최소 동전 개수를 구할 때 다시 사용할 수 있다는 것이다.
각각 a, b, c, d원 짜리 동전이 여러 개 있다고 가정하자. 위 문제와 같은 방식으로 한다면 p원을 만들기 위해 a+(p-a)원이나, b+(p-b)원 등을 만들 수 있다.
즉, a+(p-a), b+(p-b), c+(p-c), d+(p-d) 등으로 나누어 생각할 수 있다. 반복되는 계산을 막기 위해 1원부터 p원까지 위의 방법으로 차례대로 만들어 나간다.
즉 m원을 만들기 위해, m-a, m-b, m-c, m-d원을 만들기 위해 필요한 최소 개수의 동전을 찾은 뒤 그 값에 +1(그 값에 a, b, c, d원을 추가시켰으므로)을 해주기만 하면 m원을 만드는데 필요한 최소 동전의 개수를 알 수 있는 것이다.

따라서,
1원 1개 1원×1
...
4원 4개 1원×4
5원 1개 5원×1

4(5-1)원, 0(5-5)원을 만들기 위한 최소 동전의 개수가 각각 4원이 4개, 0원이 0개 이므로 여기에 +1을 해주면 5개와 1개가 나온다. 1개가 최소 동전의 개수이므로 5원을 만들 수 있는 최소 동전의 개수는 1개이다.

6원 2개 1원×1, 5원×1
7원 3개 1원×2, 5원×1
...
10원 1개 10원×1

9(10-1)원, 5(10-5)원, 0(10-10)원을 만들기 위
한 최소 동전의 개수가 각각 9원이 5개, 5원이 1
개, 0원이 0개 이므로 여기에 +1을 해주면 6개,
2개, 1개가 나온다. 1개가 최소 동전의 개수이므
로 10원을 만들 수 있는 최소 동전의 개수는 1
개이다.

80원 2개 40원×2

79(80-1)원, 75(80-5)원, 70(80-10)원, 40(8
-40)원, 30(80-50)원을 만들기 위한 최소 동전
의 개수가 각각 8개, 4개, 3개, 1개, 3개이므로
여기에 +1을 해서 가장 적은 동전의 개수는 2개
이다.

이러한 방식으로 최적 해에 점차 접근하는 방법을 DP라 한다.

반드시 DP로 풀어야 하는 것은 아니다.
( 백트래킹 + 그리드 ) 알고리즘 방식으로도 가능할 것 같다. 알고리즘은 아래와 같다.

퇴각검색은 모든 가능한 경우를 검색하는 방법으로 퇴각검색의 효율을 높이기 위해서는 먼저 그리드 알고리즘으로 동전의 개수의 상한을 설정하고 그 이후에 발견된 해 중 가장 좋은 해를 결정해야한다.
만약 동전의 종류가 1원, 5원, 10원, 40원, 50원이 있을 때 137원을 최소 동전의 개수로 바꾼다면 먼저 137원에서 동전 1원, 5원, 10원, 40원, 50원을 하나씩 바꿀 때의 5가지 경우로 나누어 생각해 본다. 그런 다음 다시 136원, 132원, 127원, 97원, 87원 중에서 다시 1원, 5원, 10원, 40원, 50원을 하나씩 바꿀 때의 각각 5가지 경우를 금액이 0원이 될 때까지 고려하는 방법이다.

퇴각검색은 모든 가능한 경우를 다 살펴보는 경우이기 때문에 시간이 다른 알고리즘에 비해 많이 소요된다. 때문에 시간을 단축하려면 간단한 그리드 알고리즘을 이용해 해를 구한 다음 이 해를 기준점으로 해서 현재 검색하고 있는 방향의 퇴각검색의 해가 그리드 알고리즘의 결과 해보다 클 때에는 더 이상 그 방향을 탐색하지 않는 pruning 기법을 이용하여 다른 방향을 검색해야 한다(N-Queen에서 불가능하면 더이상 가지 않았던 방식과 동일)

[# Dynamic Programming #]

#include <stdio.h>
#include <memory.h> //memset() / memcpy
#define MAX 100000 //잔돈 액수 제한(10만원)
#define INPUTFILE "input.txt" //이것도 define이 되는걸 처음 알게됨(06.01.19)
#define OUTPUTFILE "output.txt"

int g_Send_money, g_TValue, g_Change; //앞에서부터 준돈, 물건값, 잔돈
int Result[MAX+1][5]; //결과값 배열

//입력(from file)
void input(void)
{
FILE *pIF=fopen(INPUTFILE, "rt");
fscanf(pIF, "%d %d", &g_Send_money, &g_TValue);
g_Change = g_Send_money - g_TValue;
fclose(pIF);
}

//프로세스
void DP(void)
{
int Times[MAX+1]; //동전의 빈도수를 임시로 가지고 있을 배열(if문 비교위해)
int Money[5]={50, 40, 10, 5, 1};
int i, j;

memset(Times, 127, sizeof(Times));
Times[0]=0;

memset(Result[0], 0, sizeof(int)*5);

for (i=1; i<=g_Change; i++) //i의 범위(1 <= i <= 잔돈)
for (j=0; j<5; j++) //j는 동전배열을 돌린다(순서 : 50 -> 1)
//동전의 최소금액 <= 잔돈 && 최소 동전 개수를 체크
if (Money[j]<=i && Times[i-Money[j]]+1<Times[i])
{
//i금액을 만들어 내는 최소동전 개수 Times[i]에 저장(값 = 동전 개수)
Times[i]=Times[i-Money[j]]+1;

// printf("잔돈 = %d, Times[i] = %d\n", i, Times[i]); //중간값 임시출력(주석)

//i금액을 만드는 j동전의 종류별로 개수를 모두 누적(=Result[i])=총 동전개수
memcpy(Result[i], Result[i-Money[j]], sizeof(int)*5);

//마지막 값을 기록(각 동전별로 사용된 회수)
Result[i][j]++;
}
}

//출력(to file)
void output(void)
{
FILE *pOF=fopen(OUTPUTFILE, "wt");
fprintf(pOF, "%d\n%d\n%d\n%d\n%d\n",
Result[g_Change][0], Result[g_Change][1],
Result[g_Change][2], Result[g_Change][3],
Result[g_Change][4]);
fclose(pOF);
}

//메인
void main(void)
{
input();
DP();
output();
}


[# Backtracking + Greedy #]

이건... 내일.. 하든지... ㅠㅠ....