[Baekjoon Online Judge] 백준 2293번 동전 1(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2293번 동전 1

(C++, Python)

(글쓴날 : 2020.04.16)

 

---

* Baekjoon Online Judge, 백준 2293번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2293번 동전 1

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2293

2293번: 동전 1

---

2) 풀이 과정

* 시간 복잡도 : O(nk)

 

n가지 종류의 동전이 주어지고 동전 개수에 상관없이 k원이 되도록 만드는 경우의 수를 구하는 문제입니다.

 

동적 계획법을 적용해야 하는 문제인데 저의 경우, 도저히 점화식이 생각나지 않아 공개되어 있는 점화식을 참조하였습니다.

점화식은 제 코드 기준 memoization[j] = memoization[j- values[i]]이며,

길이가 k + 1인 memoization할 dp 테이블을 생성하였고, 각 인덱스의 값이 해당 인덱스를 k원으로 쳤을 때 사용된 동전의 경우의 수입니다.

따라서 0번째 인덱스의 경우, 0원을 만들려면 아무 동전도 사용하지 않는 한 가지 경우밖에 없으므로 1로 초기화한 뒤, 점화식을 이용한 반복문을 돌려 문제를 해결했습니다.

 

무책임하지만, 코드를 보고 저 점화식이 이해가 가지 않는다면, 그 어떤 방법보다 직접 손으로 코드의 반복문을 디버깅해가며 저 점화식이 왜 성립하는지 이해하는 방법이 제일 효과적인 것 같습니다. (제가 그랬습니다...)

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, k;
    cin >> n >> k;
 
    vector<int> values(n, 0);
    for (int i = 0; i < n; i++)
        cin >> values[i];
 
    vector<int> memoization(k + 1, 0);
    memoization[0] = 1;
 
    for (int i = 0; i < n; i++)
        for (int j = 1; j < k + 1; j++)
            if (j - values[i] >= 0)
                memoization[j] += memoization[j - values[i]];
 
    cout << memoization[k];
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
n, k = map(int, input().split())
values = [int(input()) for _ in range(n)]
memoization = [1] + [0] * k
 
for i in range(n):    
    for j in range(1, k + 1):
        if j - values[i] >= 0:
            memoization[j] += memoization[j - values[i]]
 
print(memoization[-1])

---