문제
모스 부호(Morse code)는 전화가 없던 시절 무선 전신에 주로 사용하던 코드로, 짧은 신호(단점, o)와 긴 신호(장점, -)를 섞어 글자를 표현하는 표현방식입니다. 예를 들어 알파벳 J는 모스 부호 o---로 표현되고, M은 --로 표현됩니다.
n개의 장점과 m개의 단점으로 구성된 모든 신호들을 담고 있는 사전이 있다고 합시다. 예를 들어 n = m = 2라면 다음과 같은 신호들이 포함되어 있는 것이죠.
이 신호들은 사전순서대로 정렬되어 있습니다. -의 아스키 코드는 45이고, o의 아스키 코드는 111이기 때문에 -가 먼저 오게 되죠. n과 m이 주어질 때 이 사전의 k번째 신호를 출력하는 프로그램을 작성해 봅시다. 예를 들어 위 사전에서 네 번째 신호는 o--o입니다.
입력
입력의 첫 줄에는 테스트 케이스의 수 C(≤50)가 주어집니다. 각 테스트 케이스는 세 개의 정수 n, m(1≤n, m≤100), k(1≤k≤1,000,000,000)로 주어집니다. 사전에는 항상 k개 이상의 신호가 있다고 가정해도 좋습니다.
출력
각 테스트 케이스마다 한 줄에 해당 신호를 출력합니다.
예제 입력
3
2 2 4
4 8 13
6 4 1
예제 출력
o--o
--o-ooo-oooo
------oooo
이 책에서 보던 DP문제랑 사뭇다른 형태의 문제로 느껴졌다. 그래서 왜 이 문제가 왜 DP인지 의아했었다. 사전을 직접 만들어보면서 어떤 규칙으로 작동하는지를 생각했다. 현재 k번째일때 가장 오른쪽에있는 morse[idx]는 'o'이고 morse[idx-1]은 '-'을 만족하는 idx를 찾은후, idx의 'o'를 왼쪽으로 한 칸 옮기고 idx보다 오른쪽에 있는 'o'를 맨 우측으로 이동시키면 된다. 하지만 이런 방식은 너무 단순하여 k가 10억이 될 수 있으므로 시간안에 못 풀 것이라 생각했고, 그래서 DP를 활용할 방법을 생각했다. 그렇게 떠올린 방법이 이항계수를 활용해서 쓸데없는 연산을 줄인것이다. 또한 이렇게 하면 정답을 구하는 과정에서 옮겨야 될 'o'보다 오른쪽에 있는 'o'들은 항상 맨 우측에 있는 셈이므로(처음에 ---ooo으로 시작하기 때문)더욱 효율적이었다.
처음 코드를 작성했을 때 별 다른 문제를 발견하지 못하고 제출을 했었다. 하지만 채점 결과는 오답이었다. 어디가 틀렸는지 확인하려고 몇 가지 예시를 돌려봤는데 50 50 2처럼 이항계수가 큰 숫자들이 나올경우 overflow가 발생한다는 문제점이 있었다. 문제 조건에서 k가 10억 이하라는 조건이 있었기 때문에 이항계수가 10억 보다 큰 숫자가 나오면 10억 + 1로 처리 함으로 써 overflow를 해결했지만 처음부터 overflow를 고려하지 않았던 부분이 부족하다고 생각한다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m, k;
int morse[200]; //o->1, - -> 0
int cache[200][200];
int combination(int n, int r) {
if (n == r || r == 0)
return 1;
int& ret = cache[n][r];
if (ret != 0)
return ret;
ret = combination(n - 1,r - 1) + combination(n - 1,r);
if (ret > 1000000000) //overflow가 발생하는 걸 막기위해서
ret = 1000000001;
return ret;
}
void objMorse(int currentNum) {
if (currentNum == k)
return;
int here = n + m - 1;
int cnt1 = 0;
while (!(morse[here - 1] == 0 && morse[here] == 1)) {
if (morse[here] == 1)
cnt1++;
here--;
}
cnt1++;
for (int to = 0; to < here; to++) {
int tmp = combination(here - to - 1 + cnt1, cnt1);
if (k >= currentNum + tmp) {
morse[here] = 0;
morse[to] = 1;
objMorse(currentNum + tmp);
return;
}
}
}
int main(void) {
int C;
cin >> C;
for (int i = 0; i < C; i++) {
cin >> n >> m >> k;
memset(morse, 0, sizeof(morse));
for (int j = n; j < n + m; j++)
morse[j] = 1;
objMorse(1);
for (int j = 0; j < n + m; j++) {
if (morse[j] == 0)
printf("-");
else
printf("o");
}
printf("\n");
}
return 0;
}
이 책의 코드와 나의코드를 비교했을 때 이항계수를 활용한다는 점에서 공통점이 있지만 책의 코드가 더욱 논리적이라는 생각이든다. 그만큼 나의 코드가 조잡하다는 소리이다. 부정적으로 나는 아직 부족하다고 생각할 수 있겠지만 긍정적으로 생각하면 더 발전할 여지가 남아있다고 생각할 수 도 있다.👍