[BOJ 1256 // C++] 사전

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1256번 문제인 사전이다.
문제는 아래 링크를 확인하자.

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

1256번: 사전

문자열을 맨 앞에서부터 작성해나갈 때, a를 지금 썼다고 가정할 시 뒤에 나올 수 있는 문자열의 경우의 수보다 K가 큰지 작은지에 따라 a를 쓸지 z를 쓸지 결정해나갈 수 있다.

사용할 수 있는 z를 모두 썼을 때 K값이 1(a만을 채우는 경우)이 아니라면 이는 가능한 전체 경우의 수보다 K가 크게 주어진 것이므로 -1을 출력한다.

그렇지 않은 경우 문자열을 완성하여 출력한다.

 

200개 중 100개를 고르는 경우의 수는 64비트 정수 자료형으로도 담을 수 없음에 유의하여 구현하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int comb[201][201];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 1; i <= 200; i++) {
		comb[i][0] = comb[i][i] = 1;
	}

	for (int i = 2; i <= 200; i++) {
		for (int j = 1; j < i; j++) {
			comb[i][j] = min(comb[i - 1][j - 1] + comb[i - 1][j], 1000000001);
		}
	}

	string ans = "";
	int N, M, K; cin >> N >> M >> K;
	while (M > 0) {
		if (K > comb[N + M - 1][M]) {
			K -= comb[N + M - 1][M];
			M--;
			ans += "z";
		}
		else {
			N--;
			ans += "a";
		}
	}
	
	if (M == 0) {
		if (K != 1) {
			cout << -1;
			return 0;
		}
	}

	while (N > 0) {
		ans += "a";
		N--;
	}

	cout << ans;
}