[Codeforces][Round #693][Div.3] B : Fair Division (C++)

https://codeforces.com/contest/1472/problem/B

Problem - B - Codeforces

 

[난이도] Div.3
[유형] DP

[풀이]
전체 합이 홀수인지, 짝수인지를 따져가며 풀이도 있는데 생각이 안나서 DP로 풀었다.

DP(n1,n2) : 1이 n1개, 2가 n2개 남았을 때 캔디를 동일하게 분배가 가능하면 true, 아니면 false

DP(n1,n2) = DP(n1-2,n2) A에게 1을 1개, B에게 1을 1개 준 경우
|| DP(n1-2,n2-1) A에게 1을 2개, B에게 2를 1개 준 경우
|| DP(n1,n2-2) A에게 2를 1개, B에게 2를 1개 준 경우
(위 세가지 케이스중 한가지만 true여도 DP(n1,n2)는 true가 된다.)

 

#include <cstdio>
#include <cstring>
int tc,N,a[3],dp[101][101];
int sol(int n1,int n2){
    int& ret=dp[n1][n2];
    if(ret!=-1) return ret;
    if(n1==0&&n2==0) return ret=1;
    
    if(n1-2>=0 && sol(n1-2,n2)) return ret=1;
    if(n1-2>=0 && n2-1>=0 && sol(n1-2,n2-1)) return ret=1;
    if(n2-2>=0 && sol(n1,n2-2)) return ret=1;
    return ret=0;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        a[1]=a[2]=0;
        while(N--){
            int v;
            scanf("%d",&v);
            a[v]++;
        }
        memset(dp,-1,sizeof(dp));
        if(sol(a[1],a[2])) puts("YES");
        else puts("NO");
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round693-Div.3/B.cpp