[2294번] 동전 2

문제 출처 :

https://www.acmicpc.net/problem/2294

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. BFS

동전 문제는 다른 문제로 생각해 본다면 시작점에서 도착점으로 가기위한 최단 거리를 구하는 것과 똑같다.

즉, 문제에서 나온 1, 5, 12는 한번에 이동할 수 있는 거리를 의미하고

한번 이동할 때 마다 이동 횟수를 +1해주면 된다고 생각하고 문제를 접근하면 좀 더 쉽게 생각할 수 있다.

점화식에 대해 생각해보자

            if(here + coin[i] <= k)

            {

                // DP 점화식 :: 현재 + 갈위치 = (현재+갈 위치에 이미 존재하는 값) 그리고 (현재 위치에서 +1해주는 값)중 최소

                DP[here + coin[i]] = min(DP[here + coin[i]], DP[here] + 1);

                q.push(here + coin[i]);

            }

here + coin[i] <= k

이 말은 결국 도착점보다 더 멀리 이동할 필요가 없다는 것을 의미한다.

나는 15로 가고싶은데 만약 12에 위치해 있었는데 5를 더해 17로 가면 다시 돌아올 수 없기 때문이다.

DP[here + coin[i]] = min(DP[here + coin[i]], DP[here] + 1)

DP[here + coin[i]]

원래 이 자리에 있기위한 기존에 존재하던 최소 이동 횟수를 가지고 있다.

DP[here] + 1

내가 현재 자리(DP[here])에서 coin만큼 더하여 갈 위치는 이동 횟수 + 1을 의미한다. 

min(~)

그 둘중 더 최소인 것을 구한다.

주석을 통해 나머지 내용은 서술해 두었다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <queue>
#include <limits.h>
 
#define min(a,b) (a < b ? a : b)
 
using namespace std;
 
int DP[10002];
bool visit[10002];
 
int main()
{
    int n, k;
    int coin[102];
    queue<int> q;
 
    // INT_MAX :: 만족할 수 없는 값
    fill(DP, DP + 10002, INT_MAX);
 
    scanf("%d %d", &n, &k);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &coin[i]);
 
    q.push(0);
    DP[0] = 0;
 
    while (!q.empty())
    {
        int here = q.front();
 
        // 원하는 값이 나오면 중지
        if (here == k)
            break;
 
        q.pop();
 
        // 이미 방문했는 곳은 안와도 되는 이유
        // 무조건 +1씩 진행중이기에 이미 방문한 곳을 다시 온다는 것은 이전 값보다 크다는 것
        if (visit[here] == true)
            continue;
 
        visit[here] = true;
 
        // 동전 개수만큼 for문
        for (int i = 0; i < n; i++)
        {
            // 현재위치 + 더해질 위치가 도착위치보다 작거나 같은 곳
            // (동전은 양수이기에 큰 곳을 가봤자 돌아올 수 없다.)
            if(here + coin[i] <= k)
            {
                // DP 점화식 :: 현재 + 갈위치 = (현재+갈 위치에 이미 존재하는 값) 그리고 (현재 위치에서 +1해주는 값)중 최소
                DP[here + coin[i]] = min(DP[here + coin[i]], DP[here] + 1);
                q.push(here + coin[i]);
            }
        }
    }
 
    if (DP[k] == INT_MAX)
    {
        printf("-1");
        return 0;
    }
 
    printf("%d", DP[k]);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>