[백준]1256번 사전 - C/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

---

 

'a' N개와 'z' M개를 사용하여 단어를 만드는 것은 두 단어를 '조합' 하는 방식이므로

dp[i][j] = dp[i-1][j] + dp[i][j-1] 을 통하여 'a' i개와 'b' j개를 활용하여 만들 수 있는 단어의 개수를 구할 수 있다.

이와 같이 구한 정보를 바탕으로 위 그림과 같이 앞에 'a' 를 붙이는 경우와 'z'를 붙이는 경우를 나누어 k가 위치한 곳까지 이분 탐색을 진행한다.

 

[C/C++ 풀이]

#include <iostream>

using namespace std;

int n,m,k;
int dp[101][101] = {0};
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m >> k;

	for (int i = 1; i <= 100; i++) {
		dp[i][0] = 1; 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] > 1'000'000'000) dp[i][j] = 1'000'000'000;
		}
	}
	if (dp[n][m] < k) {
		cout << -1; return 0 ;
	}
	int a_cnt = n;
	int z_cnt = m;
	for (int i = 0; i < n + m; i++) {
		int as = dp[a_cnt - 1][z_cnt];
		
		if (a_cnt == 0) {
			cout << 'z';
			z_cnt--;
		}
		else if (z_cnt == 0) {
			cout << 'a';
			a_cnt--;
		}
		else if (k <= as) {
			cout << 'a';
			a_cnt--;
		}
		else {
			k = k - as;
			cout << 'z';
			z_cnt--;
		}
	}

	return 0;
}

[Java 풀이]

import java.util.Scanner;

public class Main {
	static int n,m,k;
	static int[][] dp;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		k = sc.nextInt();
		
		setDP();
		getStr();
		
	}
	
	static void setDP() {
		dp = new int[101][101];
		dp[0][0] = 0;
		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] > 1000000000 ) dp[i][j] = 1000000000; 
			}
		}
	}
	
	static void getStr() {
		int acnt = n;
		int zcnt = m;
		int as;
		
		if(k > dp[n][m]) { 
			System.out.print(-1);
			return;
		}
		
		for(int i=0;i<n+m;i++) {
			
			if(acnt == 0) {
				System.out.print("z");
				zcnt--;
				continue;
			}
			else if(zcnt == 0) {
				System.out.print("a");
				acnt--;
				continue;
			}
			
			as = dp[acnt-1][zcnt];
			if( k <= as) {
				System.out.print("a");
				acnt--;
			}
			else {
				k -= as;
				System.out.print("z");
				zcnt--;
			}
		}
		
	}
}

---

    문제를 처음 보았을때는 쉬워 보였지만 감이 잘 잡히지 않았다. 그래서 분류를 보았는데 조합론과 DP로 분류되어 있길래 DP로 풀 방법을 생각해보았지만 실패하였다. 구글링의 힘을 빌려 검색을 좀 해보니 조합의 경우 DP 배열을 활용하여 구하는 것이었다. 그 방법으로 조금 생각해보니 문제의 풀이가 이해가 되면서 풀 수 있었다. 이전에도 조합 문제를 풀어보았을 텐데 조합을 구하는 방법을 기억해내지 못했다. 다음번부터는 기억할 수 있을 것 같다!

    자바에 익숙해지기 위해 풀었던 문제를 자바로 옮겨 적었다. 같은 알고리즘으로 작성을 하였더니 IndexOutofBound 오류가 나왔다. as = [a_cnt -1][z_cnt] 부분이었는데 생각해보니 a_cnt가 0이면 index가 -1 이 되게된다. 아마 VisualStudio 와 백준의 채점환경 모두 -1 이 인덱스로 들어오는 경우는 실제 활용하지 않으면 에러를 내지 않나보다. 옛날에도 비슷한 경우로 VS에서는 잘 나오는데 SWEA 채점환경에서는 안되는 경우가 -1 인덱스 문제였다. 이러한 부분을 유의하며 풀어야겠다!