×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,238,571명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :


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(~)

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


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



소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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 >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[2957번] 이진 탐색 트리  (0) 2017.03.06
[5637번] 가장 긴 단어  (2) 2017.03.06
[2294번] 동전 2  (0) 2017.03.06
[13913번] 숨바꼭질 4  (2) 2017.03.04
[1949번] 우수 마을  (0) 2017.03.03
[1620번] 나는야 포켓몬 마스터 이다솜  (0) 2017.03.03