Skip to content

BOJ_1256_사전 #44

Open
Open

Description

@changicho

1256. 사전

링크

난이도 정답률(_%)
Gold IV 28

설계

조합론

단어가 a와 z 두개 만 있다.

먼저 현재 index의 글자를 'a'라고 했을 때 만들어지는 경우의 수를 구한다.

이 경우의 수가 K보다 크다면 현재 index의 글자는 'a'가 된다.

만약 경우의 수가 K보다 작다면, K-=경우의 수를 수행하고 현재 index의 글자는 'z'가 된다.

현재 index에서 채울 수 있는 나머지 글자의 공간은 index+1 ~ 마지막 이다.

이 채울 수 있는 글자의 수를 empty_length, 'z'의 사용하지 않은 남은 글자 수를 z_left라고 하자.

빈 공간에서 만들어지는 글자의 수는 combi(empty_length, z_left)이다.

조합의 매우 큰 수

combination을 구할 때, 이 수가 1,000,000,00를 초과할 수도 있다.

따라서 이보다 큰 수가 combination이 되는 경우, 그냥 1,000,000,00으로 설정했다.

K번째 글자가 없는 경우

combi(총 글자수, z의 글자수) < K 인 경우 문제의 답은 -1이 된다

정리

내 코드 빠른 코드
0 ms

고생한 점

정답이 -1이 나오는 경우

현재 상황에서 만들 수 있는 배열의 수를 초과하는 경우 -1을 출력해야한다.

이 부분을 빠뜨려 틀린 답이라고 나왔다.

(런타임 에러가 발생하지 않은 이유를 모르겠다.)

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define MAX 1000000000

// first : n, last : k;
long long memo[201][101] = { 0, };

long long combi(int n, int k) {
	if (k == 0 || n == k) {
		memo[n][k] = 1;
		return 1;
	}

	if (memo[n][k] != 0) {
		return memo[n][k];
	}

	long long sum = combi(n - 1, k - 1) + combi(n - 1, k);
	if (sum > MAX) {
		sum = MAX;
	}
	memo[n][k] = sum;
	return sum;
}

void solution() {
	string answer = "";

	int N, M, K;	// K is K'th word's index
	cin >> N >> M >> K;

	int word_length = N + M;	// this is n
	int z_count = M;			// this is k

	// choose k is the count of 'z' in nCk

	for (int n = 1; n <= 200; n += 1) {
		for (int k = 1; k <= n; k += 1) {
			long long current = combi(n, k);

			if (current == MAX) {
				break;
			}
		}
	}

	if (combi(word_length, z_count) < K) {
		cout << "-1\n";
		return;
	}

	for (int length = word_length; length > 0; length -= 1) {
		if (length <= z_count || K == 0) {
			answer += "z";
			continue;
		}

		long long combi_count = combi(length - 1, z_count);

		// this is a,
		if (combi_count >= K) {
			answer += "a";
		}
		else if (combi_count < K) {
			answer += "z";
			K -= combi_count;
			z_count -= 1;
		}
	}

	cout << answer << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}

Activity

  1. added this to the day5 milestone on Jan 10, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    clear정답코드

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions