[BOJ/백준][Gold4] 12886 : 돌 그룹 (C++)

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

12886번: 돌 그룹

 

[난이도] Gold4
[유형] DP

[풀이]
dp[a][b] : 전체 돌의 개수가 T이면서 a<=b<=T-a-b 일 때, 세 개의 돌을 같게 만들 수 있으면 1,
           아니면 0을 저장

위와 같이 점화식을 세운 뒤, a<=b<=T-a-b 조건을 만족하도록 정렬해주면서
Top-Down dp 함수를 짜주면 됩니다.
이전 상태로 돌아가지 않도록 visit 배열을 선언하면 방문 여부를 체크해주었습니다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int arr[3],dp[501][501],T,visit[501][501];
int sol(int a,int b){
    if(a<=0 || b<=0 || T-a-b<=0) return 0;
    if(a==b && a==T-a-b) return 1;
    if(visit[a][b]) return 0;
    visit[a][b]=1;
    int& ret = dp[a][b];
    if(ret!=-1) return ret;

    int tmp[3];
    int A=a,B=b,C=T-A-B;

    tmp[0]=2*A,tmp[1]=B-A,tmp[2]=C;
    sort(tmp,tmp+3);
    if(sol(tmp[0],tmp[1])) return ret=1;

    tmp[0]=A,tmp[1]=2*B,tmp[2]=C-B;
    sort(tmp,tmp+3);
    if(sol(tmp[0],tmp[1])) return ret=1;

    tmp[0]=2*A,tmp[1]=B,tmp[2]=C-A;
    sort(tmp,tmp+3);
    if(sol(tmp[0],tmp[1])) return ret=1;

    return ret=0;
}

int main(){
    for(int i=0;i<3;i++) {
        scanf("%d",&arr[i]);
        T+=arr[i];
    }
    sort(arr,arr+3);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(arr[0],arr[1]));
}

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