[BOJ 백준] 사전(1256) C++, Java

 

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

1256번: 사전

 

문제 설명 : 

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.

출력 : 

첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

• 1 ≤ N, M ≤ 100
• 1 ≤ K ≤ 1,000,000,000

 

예제 입력 : 

7 4 47

예제 출력 : 

aaazazaazaz

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 사전 1256
public class Main {

	static int N, M, K;
	
	// 출력용 변수
	static StringBuilder sb = new StringBuilder();

	// dp[i][j] : a  i 개와   z   j개로 만들 수 있는 단어의 개수
	static int[][] dp;
	
	static final int MAX_NUMBER = 1_000_000_000;

	public static void main(String[] args) throws IOException {

		// 0. 파스칼의 삼각형 초기화
		
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		// 2. dp 구해놓기
		dp = new int [N+1][M+1];
		for (int i = 1; i <= N; i++) {
			dp[i][0] = 1;
		}
		for (int j = 1; j <= M; j++) {
			dp[0][j] = 1;
		}
		for (int i = 1; i <= N; i++){
			for (int j = 1; j <= M; j++) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				if (dp[i][j] >= MAX_NUMBER) {
					dp[i][j] = MAX_NUMBER;
				}
			}
		}

		// 3. K번째 문자열 구하기
		getKthString(K);

		// 4. 출력
		System.out.println(sb.toString());
		br.close();
	}


	private static void getKthString(int K) {
		int aCnt = N;
		int zCnt = M;
		
		// ** 예외 조건
		if (dp[N][M] < K) {
			sb.append("-1");
			return;
		}

		int aStartCnt;
		for (int i = 0; i < N + M; i++) {

			// **예외조건 - 한쪽 다 떨어지면 빠르게 출력하고 끝
			if (aCnt == 0) {
				sb.append("z");
				zCnt--;
				continue;
			}
			else if (zCnt == 0) {
				sb.append("a");
				aCnt--;
				continue;
			}

			// a로 시작하는지 확인
			aStartCnt = dp[aCnt - 1][zCnt];
			if (K <= aStartCnt) {
				sb.append("a");
				aCnt--;
			}
			else {
				K = K - aStartCnt;
				sb.append("z");
				zCnt--;
			}
		}
		
	}
}

 

C++ 코드 : 

// 사전 1256
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <algorithm>

#define MAX (101+3)
#define INF (1000000001)

using namespace std;

int N, M, K;	

// dp[i][j]  :  a  i개와, z j 개로 만들 수 있는 단어의 개수
// k는 10억이하이므로 초과하면 예외 처리
int dp[MAX][MAX];		

void printKthString(int K);

int main() {
	// 1. 입력
	//freopen("input.txt", "r", stdin);
	scanf("%d %d %d", &N, &M, &K);

	// 2. 준비사항 - dp[i][j]에 몇개 가능한지 기록해놓기
	// 원래는 i - N / j = M 까지
	for (int i = 1; i <= 100; i++) {
		dp[i][0] = dp[0][i] = 1;

	}
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			if (dp[i][j] >= INF) {
				dp[i][j] = 1000000000;
			}
		}
	}

	// 3. 문자열 찾아서 출력
	printKthString(K);
	
	return 0;
}

void printKthString(int K) {
	int aCnt = N;
	int zCnt = M;

	//** 예외 조건
	if (dp[N][M] < K) {
		printf("%d", -1);
		return;
	}

	int aStartCnt;
	for (int i = 0; i < N + M; i++) {

		// **예외조건 - 한쪽 다 떨어지면 빠르게 출력하고 끝
		if (aCnt == 0) {
			printf("z");
			zCnt--;
			continue;
		}
		else if (zCnt == 0) {
			printf("a");
			aCnt--;
			continue;
		}

		// a로 시작하는지 확인
		aStartCnt = dp[aCnt - 1][zCnt];
		if (K <= aStartCnt) {
			printf("a");
			aCnt--;
		}
		else {
			K = K - aStartCnt;
			printf("z");
			zCnt--;
		}

	}
}
#endif