[Algospot] 모스 부호 사전 (문제 ID : 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(≤50)가 주어집니다. 각 테스트 케이스는 세 개의 정수 n, m(1≤n, m≤100), k(1≤k≤1,000,000,000)로 주어집니다. 사전에는 항상 k개 이상의 신호가 있다고 가정해도 좋습니다.

 

출력

각 테스트 케이스마다 한 줄에 해당 신호를 출력합니다.

---

모스 부호를 직접 만들어 k번째 부호를 출력하는 문제이다.

morse 함수를 통해 n개의 단점과 m개의 장점을 사용해 문자열을 만든다.

이 함수에서 알아야 할 것은 k-1개를 건너뛰는 것이다.

따라서 전역변수 skip을 k-1로 초기화 한 후 morse를 호출한다.

따라서 기저 사례는 skip이 0보다 작아진 경우 바로 종료하는 것이고 skip이 0이 되면 그 문자열이 바로 K번째이기 때문에 출력하고 skip을 -1로 바꾼 후 종료한다.

아직 skip이 많이 남았다면 n과 m의 이항계수와 비교한다.

 

n과 m의 이항계수를 이용하는 이유는 n,m개의 단,장점을 이용해서 만들 수 있는 최대 개수가  이항계수 (n+m, n)이기 때문이다.

만약 이보다 skip이 크다면 n과 m개의 조합으로는 K번째 문자열을 찾을 수 없기 때문에 return한다.

만약 이항계수가 더 크다면 n과 m을 1씩 줄이며 morse함수를 호출한다.

이런 과정을 거친 후 n과 m이 모두 0이 되고 skip또한 0이되면 문자열을 출력하고 종료한다.

이 문제에서 dp를 활용하는 것은 이항계수를 구하는 과정 뿐이고 정작 답을 구하기 위해선 K-1개 건너뛰기라는 알고리즘?을 이용하는데, 이 방법이 다른 문제에서도 계속 활용되니 이해를 하고 넘어가야 하겠다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/MORSE.cpp

chosh95/STUDY

C++ 코드

  
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int C, N, M, K;
int dp[201][201];
int skip;
const int OVER = 1000000000 + 100; //overflow를 막기위한 값 k가 항상 10억 이하이므로 그 이상의 값은 필요없다.
void bino(int n, int m)
{
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i <= 200; i++) {
		for (int j = 0; j <= i; j++){
			if (j == 0 || j == i) {
				dp[i][j] = 1;
				continue;
			}
			dp[i][j] = min(OVER, dp[i - 1][j-1] + dp[i - 1][j]);
		}
	}
}
void morse(int n, int m, string s) 
{
	if (skip < 0) return;
	if (n == 0 && m == 0) {
		if (skip == 0) cout << s << endl;
		--skip;
		return;
	}
	if (dp[n + m][m] <= skip) {
		skip -= dp[n + m][n];
		return;
	}
	if (n > 0)		morse(n - 1, m, s + "-");
	if (m > 0) 		morse(n, m - 1, s + "o");
}
int main()
{
	cin >> C;
	while (C--) {
		cin >> N >> M >> K;
		bino(N, M);
		skip = K-1; //k-1개를 건너뛰기
		morse(N, M, "");
	}
}