백준 2293 동전 1

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

아이디어

• 가치가 클수록, 앞에서 구한 값을 재활용할 수 있음 > DP
• 접근 1. DP[K] : K원일떄 동전의 경우의 수
  • DP[K] = DP[K-동전1] + DP[K-동전2] + ...
  • 이때는 겹치는 경우의 수가 발생
  • 낮은 동전을 계산할때, 높은 동전의 경우의수가 들어가면 안됨
• 접근 2. DP[N][K] : K원일떄, N개의 종류로 구할 수 있는 경우의 수
  • DP[N][K] = DP[N-1][K-coin[N]] + DP[N-1][K-coin[N]*2] + ...
  • N번쨰 코인의 가치를 뺀 이전 N-1개의 종류로 만든 경우의 수의 합
  • 그럼 DP[N][K] 의 크기가 1e4 * 1e2 > 1e6 의 INT 발생
  • 하지만 메모리 제한이 4MB > 4*1e6 일경우 비슷하지만, 다른 프로그램 돌리는데 메모리 있어서 초과 발생
• 접근 3. DP[N] : N원일떄 경우의 수
  • 단 접근 2를 압축시켜 놓은 버전
  • K+1의 경우 K만 사용하고, 이전값을 사용하지 않음
  • 그럼 DP[N]만을 사용해서 재활용 가능
  • 단 이때, 코인을 여러번 뺴주지 말고 한번만 빼줘야함
    • 이미 한번 뺄경우, 뺀곳에 여러번 뺀 경우의 수가 담겨있음

시간복잡도 계산

• 모든 가치에 대해 : O(K)
  • 모든 종류는 각각 이전 종류를 참고함
    • 이때 최대 N번 참고
    • O(N^2)
• 총합 : O(K+N^2) = 2e4 > 가능

자료구조

• DP값 : DP[N]
  • K 최대 : 1e4
  • N 최대 : 1e2
• coin 가치 : int[]
  • 최대 1e5 > INT 가능

코드(C++)

#include <iostream>
 
using namespace std;
 
int coin[110];
int dp[10010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,K; cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> coin[i];
    
    //dp값 초기화
    fill(dp, dp+10010, 0);
    
    dp[0] = 1;
    
    for(int j=1; j<=N; j++) {
        for(int i=0; i<=K; i++) {
            if(i-coin[j] >= 0) dp[i] += dp[i-coin[j]];
        }
    }
    
    cout << dp[K] << '\n';
    
    return 0;
}
 

문제유형

• DP - 이전 종류값 만을 포함
  • dp[N][K] = N개의 종류를 가지고있을때, K가치를 가질때의 dp 값
  • 단, 이전값만을 활용하는경우, dp[N]으로 줄여서 사용할 수 있음
    • 단 한번만 빼줘야함, 뺀곳에 여러번 뺀 경우의 수가 담겨있음
  • 대표문제 : knapsack
    • https://www.acmicpc.net/problem/12865
    • 여러 종류의 아이템을 한번씩 넣을수있을때, 한정된 비용에서의 최대가치 구하는 문제
    • dp[N][K] : N개의 종류를 들고, K만큼의 무게에서의 가질수 있는 최대 가치

비슷한 문제

• https://www.acmicpc.net/problem/2293
• https://www.acmicpc.net/problem/2293
• https://www.acmicpc.net/problem/2225
• https://www.acmicpc.net/problem/12865