MORSE (중, p. 293)

2025년 10월 31일

어떻게 풀었나?#

다 풀고나서 잘 풀었다 생각했는데, 책의 답을 보니 훨씬 쉽게 풀 수 있었음.

나는 DP와 Binary Search를 써서 풀었고, 책의 풀이는 DP만 있는 풀이였음.

내가 푼 방식이 Binary Search를 써서 조금 더 빠르긴 하지만, combination 계산 시간의 시간복잡도가 같기 때문에 시간복잡도 상으론 O(N+M)으로 동일 함.

일단 장점’-’과 단점’o’의 사전 순 정렬이 계속 헷갈렸음.

그래서 일단 0과 1로 생각하기로 함. (장점이 0이고, 단점이 1임)

우선 0 N개와 1 M개로 만들 수 있는 수의 개수는 $_{N+M}C_{N}$

여기서 0을 먼저 사용하는 경우, 0 N-1개와 1 M개로 만들 수 있는 수가 되고, 그 개수는 $_{(N-1)+M}C_{N-1}$

따라서 $_{(N-1)+M}C_{N-1}$ 값이 K개라면, 0 N-1개와 1 M개로 만들 수 있는 가장 마지막 사전순 숫자가 K번째임을 의미.

만약 $_{(N-1)+M}C_{N-1}$ 값이 K보다 크다면, 0 N-1개와 1M개로 만들 수 있는 수 중 K번째가 되는 수를 찾아보면 됨.

만약 $_{(N-1)+M}C_{N-1}$ 값이 K보다 작다면, (0:N, 1:M)개로 만들 수 있는 수에서 0으로 시작하는 숫자들은 K보다 작으므로 이만큼을 건너뛸 수 있음. 따라서 (0:N, 1:M-1)개로 만들 수 있는 수에서 $K - _{(N-1)+M}C_{N-1}$번째 수를 찾으면 됨.

이를 점화식으로 나타내면 아래와 같음.

string f(int n, int m, int k) {
    if(n == 0 && m == 0) return "";
    int combs = combi(n + m - 1, n - 1);
    if(combs >= k) return "-" + f(n - 1, m, k);
    else return "o" + f(n, m - 1, k - combs);
}

근데 나는 여기서 combs≥k인 경우가 연속해서 나올 때를 생각해서 이 부분을 binary search로 찾았음.

그리고 종만북 문제 특징이, DP문제면 DP문제에만 집중하는게 아니라 부수적인 것들(약간의 센스?)을 계속 집어 넣는 느낌이 있는데, 이번 문제도 K값이 10억까지만 들어와서 Combination 구할 때 결과 값이 10억 언저리가 넘어가는 경우 10억보다 큰 수로 세팅해야하는 센스가 필요했음.

문제#

정답 코드#

binary search & dp 풀이

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[201][201];
ll MAX = 2e9;
ll Combi(int n, int r) {
    if(n==r) return 1LL;
    else if(r==0) return 1LL;
    if(dp[n][r]>0) return dp[n][r];
    ll & ret = dp[n][r];
    ret = Combi(n-1,r-1) + Combi(n-1,r);
    if(ret>=MAX) ret=MAX;
    return ret;
}
string ans_str;
void MakeAnswer(int n, int m) {
    for(int i=0; i<n; i++) {
        ans_str.push_back('-');
        //ans_str.push_back('0');
    }
    for(int i=0; i<m; i++) {
        ans_str.push_back('o');
        //ans_str.push_back('1');
    }
}
//n: '-'(0)의 개수
//m: 'o'(1)의 개수
void f(int n, int m, int k) {
    if(k==0) return;
    int lo=0, hi=n;
    while(lo <= hi) {
        int mid = (lo+hi)/2;
        ll res = Combi(mid+m,mid);
        if(res>k) hi=mid-1;
        else lo=mid+1;
    }
    int ans=lo-1;
    if(ans>=0) {
        if(k == Combi(ans+m, ans)) {
            MakeAnswer(n-ans,m);
            MakeAnswer(ans,0);
        } else {
            MakeAnswer(n-ans-1, 1);
            f(ans + 1, m - 1, k - Combi(ans + m, ans));
        }
    }
    return;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n,m,k;
        cin >> n >> m >> k;
        ans_str.clear();
        f(n,m,k);
        printf("%s\n", ans_str.c_str());
    }
    return 0;
}

dp 풀이 (책 풀이법)

#include <bits/stdc++.h>
using namespace std;
int dp[201][201];
const int INF = 0x3f3f3f3f;
int combi(int n, int r) {
    if(n == r || r == 0) return 1;
    else if(r<0 || n<r) return 0;
    int & ret = dp[n][r];
    if(ret>0) return dp[n][r];
    return ret = min(INF, combi(n - 1, r - 1) + combi(n - 1, r));
}
string f(int n, int m, int k) {
    if(n == 0 && m == 0) return "";
    int combs = combi(n + m - 1, n - 1);
    if(combs >= k) return "-" + f(n - 1, m, k);
    else return "o" + f(n, m - 1, k - combs);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tc;
    cin >> tc;
    while(tc--) {
        int n, m, k;
        cin >> n >> m >> k;
        printf("%s\n", f(n, m, k).c_str());
    }
    return 0;
}

당연히 binary search를 추가하는 방식은 쓸데없음. 그냥 이렇게 풀었었다는 기록을 남기기 위해서 적음.

그리고 어쨌든 답 안보고 풀어서 뿌듯~! 😎