BOJ 1256: 사전

요즘 DP로 기초를 탄탄히 하는 중이다. 사실 DP만 잘하면 다 잘한다고 할 수 있을 것 같다. DP는 어디에도 없고 어디에도 있다.

본론으로 돌아와, 사전은 조합론 DP 문제이다. 조합론 DP는 대부분 파스칼의 삼각형을 DP로 점화식 세워 푸는 문제들이다.

이 문제도 마찬가지다. 언뜻 보면 오버플로 때문에 "어떤 병신이 그걸 파스칼로함? ㅋㅋ"이라 생각할 수 있지만, 상한이 있기 때문에 그냥 상한 조건을 전파하고 적절한 처리를 해주면 그만이다.

즉, big 태그에 대해, 얘가 붙으면 어짜피 뭘 해도 현재 K보다 크므로 a붙이고... 이런 식이다. 

코드를 보자. 코드가 직관적이라 이해하긴 쉬울 듯하다.

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
typedef long long int ll;
ll N, M, K;
ll C[201][201];
bool big[201][201];
string s;
int main(){
	for(int i=0;i<201;i++) memset(big[i], false, sizeof(big[i]));
	cin >> N >> M >> K;
	for(int i=0;i<201;i++){
		C[i][0]=1; 
		C[i][i]=1;
	}
	for(int i=2;i<=200;i++){
		for(int j=1;j<=i/2;j++){
			C[i][j]=C[i-1][j-1]+C[i-1][j];
			if(big[i-1][j-1] or big[i-1][j]){
				big[i][j]=true;
			}
			else if(C[i][j]>INF){
				big[i][j]=true;
			}
			C[i][i-j]=C[i][j];
			big[i][i-j]=big[i][j];
		}
	} // Overflow;; 자명히
	int A=N, Z=M; // A, D의 개수
	if(!big[A+Z][Z] and K>C[A+Z][Z]){
		cout << "-1";
		return 0;
	} // 미리 처리: big면 무조건 포함
	K--;
	for(int i=0;i<N+M;i++){
		if(A==0){
			s+="z";
			Z--;
			continue;
		}
		else if(Z==0){
			s+="a";
			A--;
			continue;
		}
		if(big[A+Z-1][Z]){
			s+="a";
			A--;
		}
		else if(K>=C[A+Z-1][Z]){
			s+="z";
			K-=C[A+Z-1][Z];
			Z--;
		}
		else if(K<C[A+Z-1][Z]){
			s+="a";
			A--;
		}
	}
	cout << s;
}

 

확률과 통계를 배우지 않은 PS인은 없으리라 믿는다.

사실 나도 확통을 못해서 색상환을 틀려먹은거긴 한데, 무튼.

행복한 한글날? 되세요 / ^ o ^ /