[BOJ/백준][Gold4] 3908 : 서로 다른 소수의 합 (C++)

https://www.acmicpc.net/problem/3908

3908번: 서로 다른 소수의 합

 

 

[난이도] Gold4
[유형] DP

[풀이]
DP[n][k] : k개의 서로 다른 소수를 선택해서 n을 만들 수 있는 경우의 수
동전 거스름돈 문제와 비슷하게 풀면 된다.
다른 점은 꼭 k개의 소수만 사용해야 한다는 점이다.
1번만 사용해야 하기 때문에 두 번째 for문에서for(int i=n;i>1;i--) 와 같이 반대로
구하고 있다. 왜냐하면 앞에서부터 증가시키면 어떤 수 i를 구할 때 i-k를 구했을 때 prime[j]가
이미 포함되었음에도 중복해서 포함될 수 있기 때문이다.

 

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector<int> prime;
int T,n,k,dp[1121][15];
int main(){
    scanf("%d",&T);
    prime.push_back(2);
    for(int i=3;i<=1120;i++){
        bool ok=1;
        for(int j=2;j<i;j++){
            if(i%j==0) {
                ok=0;
                break;
            }
        }
        if(ok) prime.push_back(i);
    }
    printf("size:%d\n",prime.size());
    for(auto k : prime) printf("%d ",k);
    puts("");

    while(T--){
        scanf("%d%d",&n,&k);
        memset(dp,0,sizeof(dp));
        for(int j=0;j<prime.size();j++){
            if(prime[j]>n) break;
            for(int i=n;i>1;i--){
                if(i-prime[j] < 0) continue;
                if(i==prime[j]) {
                    dp[i][1]=1;
                    continue;
                }
                for(int l=2;l<=k;l++){
                    dp[i][l]+=dp[i-prime[j]][l-1];
                }
            }
        }
        printf("%d\n",dp[n][k]);
    }
    
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/3908.cpp