문제 : https://algospot.com/judge/problem/read/MORSE
알고리즘 문제 해결 전략 1권 p.293
[알고리즘 STEP. 1]
일단 '-' 와 'o'를 이용해서 만들수 있는 모든 조합을 모두 찾아서 해당 순서 k에 해당하는 문자열만 출력했다.
n개의 o와 m개의 -로 모스부호를 만들며, 사전순이므로 -가 o보다 앞에 나와야 한다.
* void play(int n, int m, string ret)
ret이라는 주어진 문자열에 n개의 o와 m개의 -로 만든 모스부호를 이어붙이는 함수이다.
n==0, m==0이라면 주어진 문자를 모두 사용하여 하나의 문자열을 완성한 것이다. 하나의 문자열을 완성할 때 마다 k를 하나씩 줄여가면, k==1일 때 원하는 타겟 문자열을 출력할 수 있다.
- '-'와 'o'를 어떻게 붙여나갈지?
-와 o를 어떻게 붙여나갈지 이해를 돕기 위해 n=2, m=2으로 만들 수 있는 모스부호를 순서대로 적어보았다.
사전순대로 출력을 하면 아래와 같이 '-'로 시작하는 모든 문자열이 먼저 나오고 그 다음에 'o'로 시작하는 모든 문자열이 나온다.
다시 '-'로 시작하는 문자열들을 보면, '-'로 시작하는 모든 문자열이 먼저 나오고 그 다음에 'o'로 시작하는 모든 문자열이 나온다.
이러한 규칙을 이용해서 사전 순서대로 모스부호를 만드는 코드를 작성해보자
일단 '-'가 1개 이상 남아있다면, 인자로 받은 문자열 ret (= 지금까지 만든 문자열. 예를들어 위의 3개의 문자열의 경우에는 ret은 "-"이다) 뒤에 -를 붙여주고 남은 문자들로 문자열을 다시 이어붙인다. '-'로 시작하는 문자열이 끝났다면 'o'로 시작하는 것도 같은 방법으로 만들어준다.
이 부분코드는 아래와 같다.
if(n!=0) play(n-1, m, ret+"-");
if(m!=0) play(n, m-1, ret+"o");
//https://algospot.com/judge/problem/read/MORSE
#include <iostream>
#include <vector>
#include <cstring>
#define FOR(i, ed) for(int i = 0 ; i < ed; i++)
using namespace std;
int tc;
// input
int n, m, k;
//n개의 -, m개의 o로 k번째 모스부호를 반환
void play(int n, int m, string ret){
if(n==0 && m==0){
if(k==1) cout << ret << endl;
k--;
return;
}
if(n!=0) play(n-1, m, ret+"-");
if(m!=0) play(n, m-1, ret+"o");
}
int main(){
freopen("input.txt", "r", stdin);
cin >> tc;
while(tc--){
cin >> n >> m >> k;
play(n, m, "");
}
} |
[알고리즘 STEP. 2]
위의 방법으로 정답까지는 구할 수 있지만, 구하려는 문자열이 길고 k가 큰 수인 경우 시간이 오래 걸린다.
n개의 -와 m개의 o으로 총 몇 개의 문자열을 만들 수 있는지는 조합으로 구할 수 있다.
(n개의 '-'와 m개의 'o'으로 만들 수 있는 문자열의 수) = (n+m)! / n!*m! = (n+m)Cn
이를 활용해서 불필요한 k-1개의 문자열을 건너뛰고 바로 k번째 문자열을 출력하도록 해보자.
* void calcComination()
이 함수는 n,m <= 200 까지의 모든 조합을 미리 계산해둔다.
이 내부 로직(combination[i][j] = combination[i-1][j] + combination[i-1][j-1])은 파스칼의 삼각형을 따른다.
200C100을 하면 수가 int범위를 넘어간다. 이 오버플로우를 피하기 위해서 k의 최대값인 1000000000 + 100 보다 커지면 k의 최대값을 대신 저장하도록 한다. 어차피 이 이상의 수를 건너뛸 일이 없기 때문이다.
* void play2(int n, int m, string ret)
이 함수는 n, m에 대해 n+mCn의 값이 건너 뛰고자 하는 값 k보다 작다면 그만큼을 건너뛰고 그 이후부터 다시 문자열을 만든다.
if(combination[n+m][n] < k){
k -= combination[n+m][n];
return;
}[내가 헤맨 부분]
- k == 1 에 도달하고 나서도 함수는 모든 가능한 문자열을 만들 떄까지 재귀적으로 동작한다. 코드를 짤 때 이 부분을 생각하지 못해서 k가 1보다 작아졌을 때의 탈출조건(if(k<=0) return;)을 적지 않아서, 시간초과가 계속 떴다.
- 이항계수 구하기. 조합의 수학식대로 펙토리얼을 이용해서 계산하려고 했는데, 파스칼의 삼각형을 이용하여 쉽게 구할 수 있었다.
[최종코드]
//https://algospot.com/judge/problem/read/MORSE
#include <iostream>
#include <vector>
#include <cstring>
#define FOR(i, ed) for(int i = 0 ; i < ed; i++)
using namespace std;
int tc;
// input
int n, m, k;
int combination[201][201]; // [n][m]의 중복조합 값
const int M = 1000000100; // k의 최대 값 +1.
void calcComination(){
memset(combination, 0, sizeof(combination));
FOR(i, 201){
combination[i][0] = combination[i][i] = 1;
for(int j=1; j<i; j++)
combination[i][j] = min(M, combination[i-1][j] + combination[i-1][j-1]);
}
}
//n개의 -, m개의 o로 k번째 모스부호를 반환
void play2(int n, int m, string ret){
if(k<=0) return; //????????
if(n==0 && m==0){
if(k==1) cout << ret << endl;
k--;
return;
}
if(combination[n+m][n] < k){
k -= combination[n+m][n];
return;
}
if(n!=0) play2(n-1, m, ret+"-");
if(m!=0) play2(n, m-1, ret+"o");
}
int main(){
// freopen("input.txt", "r", stdin);
cin >> tc;
calcComination();
while(tc--){
cin >> n >> m >> k;
play2(n, m, "");
}
} |
[더 간단한 알고리즘]
주어진 n과 m으로 문자열을 만들 때, '-'로 시작하는 문자열의 수는 n-1개의 '-'와 m개의 'o'로 만들 수 있는 모든 문자열의 수(X라고 하자)와 같다.
만약 k가 X보다 작다면 '-'로 시작하는 문자열 X개 안에 찾으려는 문자열이 있다는 뜻이므로, 이 X개 안에서만 찾아보면 된다.
if(k <= combination[n+m-1][n-1])
return "-"+play3(n-1, m);
반대로 만약 k가 X보다 크다면, '-'로 시작하는 문자열 X개 안에는 찾으려는 문자열이 없다는 뜻이다. 그러므로 '-'로 시작하는 문자열 X개는 건너뛰고 바로 'o'로 시작하는 문자열들을 만들면 된다.
k -= combination[n+m-1][n-1];
return "o"+play3(n, m-1);
string play3(int n, int m){ if(n==0) return string(m, 'o');
if(k <= combination[n+m-1][n-1])
return "-"+play3(n-1, m);
k -= combination[n+m-1][n-1];
return "o"+play3(n, m-1);
} |
[최종코드 2]
//https://algospot.com/judge/problem/read/MORSE
#include <iostream>
#include <vector>
#include <cstring>
#define FOR(i, ed) for(int i = 0 ; i < ed; i++)
using namespace std;
int tc;
// input
int n, m, k;
int combination[201][201]; // [n][m]의 중복조합 값
const int M = 1000000100; // k의 최대 값 +1.
void calcComination(){
memset(combination, 0, sizeof(combination));
FOR(i, 201){
combination[i][0] = combination[i][i] = 1;
for(int j=1; j<i; j++)
combination[i][j] = min(M, combination[i-1][j] + combination[i-1][j-1]);
}
}
string play3(int n, int m){
if(n==0) return string(m, 'o');
if(k <= combination[n+m-1][n-1])
return "-"+play3(n-1, m);
k -= combination[n+m-1][n-1];
return "o"+play3(n, m-1);
}
int main(){
// freopen("input.txt", "r", stdin);
cin >> tc;
calcComination();
while(tc--){
cin >> n >> m >> k;
cout << play3(n, m) << endl;
}
} |
