모스 부호 사전

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

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

4개의 신호로 이루어져있을 때 첫번째 코드가 ‘-‘ 이라면:

나머지 3개의 신호는 ‘-‘ 1개 ‘o’ 2개로 구성이되고 이때 만들 수 있는 신호의 가지 수를 구한다. 이때의 가지수가 k 보다 같거나 크다면 첫번째 신호는 ‘-‘ 으로 시작한다. 반대로 ‘-‘ 으로 시작하는 가지수보다 k가 크다면 ‘o’ 으로 시작함을 알 수 있다.

d[n+m][m]: n+m 개로 구성된 신호 중 m 개의 단점으로 구성된 신호 가지 수로 정의
첫 신호가 ‘-‘ 일 경우, 나머지 3가지 신호는 두번 째 신호가 ‘-‘ 일 경우와 아닌 경우로 나눌 수 있다.
d[2+2][2] = d[1+2][1] + d[1+2][2]

d[n+m][m] = d[n+m-1][m-1] + d[n+m-1][m]
즉, 조합 수와 같다: d[n][r] = d[n-1][r-1] + d[n-1][r]

4개 중 2개를 뽑는 경우의 수 = 6가지, 4C2 = 4! / (4-2)! * 2!
nCr = n! / ((n- r)! * k!)

// nCr = n-1Cr + n-1Cr-1
if (n == r || r == 0) {
    return 1;
}