모스 부호 사전 (MORSE) :: 알고스팟

문제 : https://algospot.com/judge/problem/read/MORSE

algospot.com :: MORSE

 

문제

 

모스 부호(Morse code)는 전화가 없던 시절 무선 전신에 주로 사용하던 코드로, 짧은 신호(단점, o)와 긴 신호(장점, -)를 섞어 글자를 표현하는 표현방식입니다. 예를 들어 알파벳 J는 모스 부호 o---로 표현되고, M은 --로 표현됩니다.

n개의 장점과 m개의 단점으로 구성된 모든 신호들을 담고 있는 사전이 있다고 합시다. 예를 들어 n = m = 2라면 다음과 같은 신호들이 포함되어 있는 것이죠.

--oo -o-o -oo- o--o o-o- oo--

 

이 신호들은 사전순서대로 정렬되어 있습니다. -의 아스키 코드는 45이고, o의 아스키 코드는 111이기 때문에 -가 먼저 오게 되죠. n과 m이 주어질 때 이 사전의 k번째 신호를 출력하는 프로그램을 작성해 봅시다. 예를 들어 위 사전에서 네 번째 신호는 o--o입니다.

 

 

 

코드 ( C++) 종만북 참조

 

	#include <iostream>
	#include <string>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	int skip;
	int n,m,k;
	// k의 최대값 + 100. 오버플로를 막기 위해 이보다 큰 값은 구하지 않는다.
	const int MAX = 1000000000 + 100;
	int bino[201][201];
	//필요한 모든 이항계수를 미리 계산한다.
	void precalc()
	{
	for (int i = 0; i <= 200; ++i) {
	bino[i][0] = bino[i][i] = 1;
	for (int j = 1; j < i; ++j) {
	bino[i][j] = min(MAX, bino[i - 1][j - 1] + bino[i - 1][j]);
	}
	}
	}
	void solve(int n, int m, string s)
	{
	if (skip < 0)
	return;
	if (n == 0 && m == 0)
	{
	if (skip == 0)
	cout << s << "\n";
	skip--;
	return;
	}
	if (bino[n + m][n] <= skip)
	{
	skip -= bino[n + m][n];
	return;
	}
	if (n > 0)
	solve(n - 1, m, s + "-");
	if (m > 0)
	solve(n, m - 1, s + "o");
	}
	int main()
	{
	int C;
	cin >> C;
	precalc();
	while (C--) {
	cin >> n >> m >> k;
	skip = k - 1;
	string s = "";
	solve(n, m, s);
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub