[BOJ/백준][Gold3] 1943 : 동전 분배 (C++)

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

1943번: 동전 분배

 

 

[난이도] Gold3
[유형] DP

[풀이]
N개의 물건이 1개 이상일 수 있는 배낭 문제입니다.
기본적인 배낭 문제의 풀이와 같으며,
다른 점은
{물건의 가치, 물건의 개수} pair로 N개를 저장한 뒤
i번 물건을 1,2,3,, (총 개수) 만큼 사용해볼 때의 모든 경우를 고려해주면 됩니다.
3중 for문이 나오기 때문에 시간초과에 걸릴 수 있어 답을 찾은 즉시 종료해주어야 합니다.

 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int N,total,dp[50001];
pair<int,int> a[100];
int sol(){
    memset(dp,0,sizeof(dp));
    total=0;
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        total+=a[i].first * a[i].second;
    }
    if(total%2) return 0;
    dp[0]=1;
    for(int i=0;i<N;i++){
        for(int j=total/2;j>=0;j--){
            if(dp[j]) continue;
            int cur=0;
            for(int k=0;k<a[i].second;k++){
                cur+=a[i].first;
                if(j-cur>=0)  dp[j]=dp[j-cur];     
                if(dp[total/2]) return 1;
            }
        }
    }
    return dp[total/2];
}
int main(){
    int tc=3;
    while(tc--) {
        scanf("%d",&N);
        printf("%d\n",sol());
    }
}

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