공항,암호코드

<공항>

1. 1<=i<=G 인 i번에만 비행기를 도킹할 수 있다.

2. k번인 첫번째 비행기가 도착한다고 하자. 비행기는 k에 도킹한다.

3. k-1과 k를 union한다. 

...반복

n. if parent of k-1 is 0 then finish 

#include <iostream>
using namespace std;
int G[100001];int p[100001];
int find(int x){
	if(p[x]==-1) return x;
	return p[x]=find(p[x]);
}
bool Union(int v){
	v=find(v);
	if(v==0) return false;
	p[v]=v-1;

	return true;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int G,P,ans=0;
	cin>>G>>P;
	for(int i=0;i<=G;i++) p[i]=-1;
	for(int i=1;i<=P;i++){
		int n;cin>>n;
		if(Union(n)) 
			ans++;
		else break;
	}
	cout<<ans;
	return 0;
}

<암호코드>

dp[k][n] : (문자열 s에서) k번째 문자와 n(이전에 넘겨받은 문자가 있으면 0이 아님)일 때 암호의 가짓수

#include <iostream>
#include <cstring>
using namespace std;
int dp[5001][27];
string s;
bool isRight(int k,int n){
	string tmp="";
	tmp=to_string(n)+s[k];
	if(stoi(tmp)<27) return true;
	return false;
}
int sol(int k,int n){
	if(n==0 &&(s[k]-'0')==0) return 0;

	if(k==s.length()-1) {
		if(n==0) return 1;
		else if(isRight(k,n)) return 1;
		else return 0;
		}
	int &ret=dp[k][n];
	if(ret!=0) return ret% 1000000;
	
	if(n!=0) {
          if(isRight(k,n)) ret+=sol(k+1,0)% 1000000;
	}
	else{
		ret+=(sol(k+1,0)% 1000000+sol(k+1,s[k]-'0')% 1000000);
	} 
	return ret;
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>s;
	int x=s.length();
	cout<<sol(0,0)% 1000000;
	return 0;
}

for(int i=0;i<n;i++){
	if(A[i]-'0'!=0) dp[i]+=dp[i-1]%MOD;
    int k=(A[i-1]-'0') *10+A[i-1]-'0'>10;
    if(k>=10&&k<26) dp+=dp[i-2]%MOD;
}