14552

해결방법

0) 1 to 9 중에서 하나를 추가함

1) 머리로만 구성되는 경우

2) 머리 1개로 구성되는 경우

2-1) 머리 한개를 선택(1 to 9중에서)

2-2) dp 재귀식 처럼 몸통의 갯수를 구함.

4개가 아니면 false

아래는 소스코드이다.

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

int data[10];

int findBody(int pos){

if(pos>9) return 0;

int ret=0;

if(data[pos]==0)

ret = max(ret,findBody(pos+1));

else{

if(data[pos]>=3){

data[pos]-=3;

ret = max(ret, findBody(pos)+1);

data[pos]+=3;

}

if(pos<8 && data[pos]>=1 && data[pos+1]>=1 && data[pos+2]>=1){

data[pos]-=1; data[pos+1]-=1; data[pos+2]-=1;

ret = max(ret, findBody(pos)+1);

data[pos]+=1; data[pos+1]+=1; data[pos+2]+=1;

}

}

return ret;

}

bool findWait(){

int cnt=0;

for(int i=1;i<10;i++) if(data[i]==2) cnt++;

if(cnt==7) return true;

for(int i=1;i<10;i++){

if(data[i]>=2){

data[i]-=2;

if(findBody(1)==4){

data[i]+=2;

return true;

}

data[i]+=2;

}

}

return false;

}

int main(){

freopen("sample.txt","r",stdin);

for(int i=0,a;i<13;i++){

scanf("%d",&a);

data[a]++;

}

int ret=0;

for(int i=1;i<10;i++){

if(data[i]<4){

data[i]+=1;

if(findWait()){

printf("%d ",i);

ret++;

}

data[i]-=1;

}

}

if(ret==0) printf("-1\n");

return 0;

}