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원이 만들어집니다.
      • …
• 정리하자면, 현재 꺼낸 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)

• 바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.

디버깅(x)

좋은 코드

최적화