[알고스팟] 모스 부호 사전

문제 링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • MORSE
  • 2000ms
  • 65536kb
  • 2281
  • 641 (28%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

모스 부호(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개 이상의 신호가 있다고 가정해도 좋습니다.

출력

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

예제 입력

3
2 2 4
4 8 13
6 4 1

예제 출력

o--o
--o-ooo-oooo
------oooo

어떻게 풀까?

이 문제는 사전순으로 정렬됐을때, k 번째의 답을 구하는 것과 유사한 문제입니다.

위 문제는 크게 2가지의 경우로 나누어 볼 수 있습니다!

1. 첫 번째로 '-'가 온다.

2. 두 번째로 'o'가 온다.

만약, 장점이 n이고, 단점이 m이라고 했을 때, 총 만들 수 있는 경우의 수를 count(n,m)이라고 합시다!

그러면 첫 번째 경우의 개수는 count(n-1, m)이고, 두 번째 경우는 count(n, m-1) 이 될 것입니다!

그런데, 다시 한번 잘 생각해보면, count의 개수를 쉽게 구할 수 있습니다!

총 n과 m의 길이에서 n개의 위치를 구하는 문제이기 때문에 이항 계수 를 구하면 됩니다!

그렇다면 맨 앞에 'o'가 오는 경우는 언제일까요?

바로! 맨 앞에 '-'가 왔던 경우의 수들 보다 큰 경우 입니다!

'-'를 고를 수 있는 경우의 수들 보다 답으로 내야하는 경우의 수가 크다면, 결국 '-'를 맨 앞에 넣더라도 답이 없다는 것이므로,

해당 개수만큼 세는 경우를 스킵할 수 있습니다!

즉, 맨 앞에 '-'를 넣었기 때문에, 해당 개수는 이 될 것입니다!

그렇다면, n번의 장음과 m번의 단음이 남았고, k번째 답을 골라야할 경우를 choose(n, m, k)라고 합시다!

그렇다면

식을 얻을 수 있습니다.

이를 이용해서 코드를 작성해 봅시다!

시간 복잡도는 우선, 이항 계수를 구하기 위해 O(nm)의 시간이 소요됩니다.

다음에는 choose에서 부분 문제가 n+m개가 나오고 부분문제를 계산할 때 상수 시간이 들기 때문에 O(n +m)이 됩니다.

따라서, 시간복잡도는 O(nm)입니다.

아참! 이항 계수는 굉장히 큰 값이 나오기 때문에 long long을 쓰더라도 오버플로우가 발생합니다!

하지만, k의 값이 10^9 이하이고, 다행히 k를 이용하여 대소 비교만 하기때문에 이항 계수에는 10^9 + 1보다 큰 수가 들어가면 

10^9 + 1을 넣어주기만 하면 코드는 문제없이 작동합니다!

이를 이용하는 것도 하나의 팁이라는 사실!

코드

#include<cstdio>
 
long long morse[101][101], n, m;
long long k;
 
 
int MORSE()
{
    int t;
    const char c[2] = { 'o', '-' };
 
    char res[201] = { 0 };
 
    for (int i = 0; i < 101; i++)
    {
        morse[i][0] = morse[0][i] = 1;
    }
 
    for (int i = 1; i < 101; i++)
    {
        for (int j = 1; j < 101; j++)
        {
            //오버 플로우 조심
            morse[i][j] = (morse[i - 1][j] + morse[i][j - 1]) > 1000000000000 ? 1000000000000 : (morse[i - 1][j] + morse[i][j - 1]);
        }
    }
 
    scanf("%d\n", &t);
 
    while (t--)
    {
        scanf("%lld %lld %lld\n", &n, &m, &k);
        int idx = n + m;
    
        for (int i = 0; i < idx; i++)
        {
            // 장점이 남지 않았음.
            if (n == 0)
            {
                res[i] = 'o';
            }
            //맨 앞이 단점
            else if (k > morse[n-1][m])
            {
                k -= morse[n-1][m];
                m--;
                res[i] = c[0];
            }
            //맨 앞이 장점
            else
            {
                n--;
                res[i] = c[1];
            }
        }
        res[idx] = 0;
        printf("%s\n", res);
    }
    return 0;
}