[종만북]9.동적 계획법 테크닉-모스 부호 사전

문제

출처 : https://www.algospot.com/judge/problem/read/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개 이상의 신호가 있다고 가정해도 좋습니다.

출력

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

풀이(책 참고)

n개의 장점과 m개의 장점으로 만들 수 있는 신호 조합은 nCm 개이다(이항계수). 먼저 이러한 조합을 전부 만드는 완전탐색 함수를 구현한다. 현재 신호 단어가 s이고 나머지 만들어야 할 신호 중 남은 장점과 단점이 각각 a개, b개일 때 다음과 같이 구현할 수 있다.

static void Morse(String s, int a, int b) {
		if (a == 0 && b == 0) {
				System.out.println(s);
		}
		if (a > 0)
			Morse(s + "-", a - 1, b);
		if (b > 0)
			Morse(s + "o", a, b - 1);
	}

a개와 b개에 대해 장점이 우선이므로 재귀호출을 통하여 각각 a-1개와 b-1개에 대한 호출을 통해 사전 순으로 문자를 출력할 수 있다. 이 때, a와 b가 0이 될때가 신호가 완성된 경우인데, k번째 신호는 a와 b가 0일 때 특정 변수를 통해 카운팅하여 k번째일 떄 출력하도록 구현하면 k번째 신호를 알아낼 수 있다.

static void Morse(String s, int a, int b) {
		if (skip < 0)
			return;
		if (a == 0 && b == 0) {
			if (skip == 0)
				System.out.println(s);
			skip--;
		}
		if (a > 0)
			Morse(s + "-", a - 1, b);
		if (b > 0)
			Morse(s + "o", a, b - 1);
	}

전역변수 skip에 k-1을 넣는다면 신호 완성시 skip을 1씩 줄여 0이 될 때 k번째 신호를 출력하도록 한다. 이후의 경우 기저사례로 skip<0일 때 종료하도록 설정하는데, 이렇게 구현하는 경우 처음부터 k번째까지 일일이 완성해야가는 비효율성이 존재하므로, 이를 효율적으로 건너뛰기 위해 이항계수를 활용한다. 함수에서 각각 a개와 b개의 점이 남았을 때 나머지 문자를 조합하는 경우의 수는 (a+b)Ca이다. 이 때, k번째 답을 찾기 위해 저장된 변수 skip이 해당 이항 계수보다 크거나 같은 경우는 답을 아직 못찾은 경우를 의미한다. 즉, 현재 호출지점에서 재귀호출을 진행하여도 답을 못찾는 경우를 의미하는데, 이런 경우 해당 값을 skip에서 빼고 실행을 생략하여 보다 효과적으로 실행시킬 수 있다.

// 오버플로를 막기위해 최댓값 M(10억)으로 범위를 제한
static void caclBino() {
		for(int i=0;i<=200;i++) {
			bino[i][0] = bino[i][i] = 1;
			for(int j=1;j<i;j++)
				bino[i][j] = Math.min(M,bino[i-1][j-1]+bino[i-1][j]); 
		}
	}
static void Morse(String s, int a, int b) {
		if (skip < 0)
			return;
		if (a == 0 && b == 0) {
			if (skip == 0)
				System.out.println(s);
			skip--;
		}
		if(bino[n+m][n]<=skip) {
			skip-=bino[n+m][n];
			return;
		}
		if (a > 0)
			Morse(s + "-", a - 1, b);
		if (b > 0)
			Morse(s + "o", a, b - 1);
	}

calcBino함수를 통해 bino 배열에 각각의 이항계수를 저장해놓고(파스칼의 삼각형 원리를 활용한다), 남은 장점과 단점의 개수가 모두 0이 아닌경우, a와 b를 통해 나머지 조합의 수를 계산하여 skip보다 같거나 작은경우 skip에서 해당 값을 빼고 이후 재귀호출 단계를 생략하도록 한다. 따라서 건너뛰는 방식을 통해 좀더 빠르게 구현할 수 있다.

여기서 보다 간단하게 구현하는 아이디어는, 함수를 바꾸어 a개 장점과 b개 장점이 남은 경우 중 skip개를 건너뛰고 제일 먼저 오는 신호를 반환하는 함수를 구현한다. 남은 신호 중 첫 글자가 장점인 경우, 나머지 부분에는 a-1개의 장점과 b개의 장점이 오므로 나머지 경우는 (a+b-1)C(a-1)개가 된다. 이때, 해당 경우의 수가 skip보다 작거나 같은 경우, 이러한 경우들은 건너뛰고 원하는 답의 맨 앞신호가 단점임을 알 수 있다. 따라서 (skip-이항계수)만큼 skip값을 빼서 건너뛰도록 한다면 다음과 같이 함수를 구현할 수 있다.

static String Morse(int a, int b, int skip) {
		if(a==0) {
			String ans = "";
			for(int i=0;i<b;i++) {
				ans+="o";
			}
			return ans;
		}
		if(skip<bino[a+b-1][a-1])
			return "-"+Morse(a-1, b, skip);
		return "o"+Morse(a,b-1,skip-bino[a+b-1][a-1]);
				
	}

기저사례로 남은 장점의 개수가 0개인 경우 나머지는 모두 단점이므로 b개만큼 단점을 출력하도록 하고, 이외의 경우에서 건너뛰어야할 개수 skip과 맨 앞이 장점인 경우 (a+b-1)C(a-1)개를 비교하여 skip보다 작거나 같다면 맨 앞이 장점인 경우들을 건너뛰고 단점부터 시작하여 a개와 b-1개에 대해 (skip-해당 이항계수)개 만큼 건너뛰도록 재귀호출하고, 아닌 경우 맨 앞에 장점을 배치하여 나머지 a-1개와 b개에 대해 skip개만큼 건너뛰도록 한다.

Menu

문제

입력

출력

풀이(책 참고)