BOJ
BOJ::2293 동전 1
BOJ Silver 1
BOJ::2293 동전 1
- Link : BOJ::2293
- Link : sihyungyou
- Level : Silver1
- tag : DP
시사점
- 좋은 DP 문제입니다.
- 글 쓰는 공돌이님의 블로그를 참고하였습니다.
키
이해(x)
- 최대 100 종류의 동전이 주어집니다.
- 각 동전의 갯수를 무한히 사용할 수 있다고 할떄, 각 동전을 적절히 조합하여 합이 k인 경우의 수를 출력합니다.
- 이때, k의 범위는 [1, 10000] 입니다.
설계, 손 코딩(x)
- 손으로 중심이 되는 코드를 구현합니다.
- n과 k를 size를 보면 알 수 있다시피, backtrack 보내면 TLE인 문제입니다.
- dp를 이용하는 방법은 항상 신선한 것 같습니다.
- dp[i] = i원을 만들 수 있는 경우의 수
- for문을 통해 동전을 하나씩 꺼내어 사용합니다.
- 꺼내어진 해당 동전에 대해,
- 해당 동전을 사용하여 경우의 수를 하나 늘릴 수 있는 k이하의 합을 업데이트 해줍니다.
- 즉 5원을 꺼낸경우( k = 10일때 ),
- 5, 6, 7, 8, 9, 10 에 대해 경우의 수를 업데이트 할 수 있습니다.
- dp[5] += dp[0]; // 합이 0원인 경우 +5원을 하면 5원이 만들어집니다.
- dp[6] += dp[1]; // 합이 1원인 경우 +5원을 하면 6원이 만들어집니다.
- …
- for문을 통해 동전을 하나씩 꺼내어 사용합니다.
- 정리하자면, 현재 꺼낸 coin의 값이 x라고 할때,
- 업데이트 할 수 있는 값들은, 합이 x이상인 경우의 수들입니다.
복잡도
- O(N)
손 코딩 후 문제 리뷰(x)
- 빼먹고 손 코딩 한 것이 있는지 확인합니다.
구현(x)
함수 List
업데이트 되는 변수
- 대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.
실제 구현
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXN = 100;
using namespace std;
int n, k;
int coin[MAXN], dp[MAXN];
void process(){
cin >> n >> k;
rep(i, 0, n) cin >> coin[i];
dp[0] = 1;
for(int i = 0; i < n; i++)
for(int j = coin[i]; j <= k; j++)
dp[j] += dp[j-coin[i]];
cout << dp[k] << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
return 0;
}
구현 후 코드리뷰 + 예제 돌려보기(x)
- 바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.