이모저모
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;
}