[Baekjoon/C++] 12101번 - 1, 2, 3 더하기 2

[백준] Baekjoon Online Judge

문제로 이동

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

이를 사전순으로 정렬하면 다음과 같이 된다.

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다.

 

출력

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.

 

---

풀이

#include <iostream>
#include <string>
using namespace std;

int n, k, cnt = 0;

void dfs(int sum, string s);

void dfs(int sum, string s) {
    if (sum == n) {
        if (++cnt == k) {
            cout << s << '\n';
            exit(0);
        }

        return;
    }

    for (int i = 1; i < 4; i++) {
        if (sum == 0)
            dfs(sum + i, s + to_string(i));
        else if (sum + i <= n)
            dfs(sum + i, s + "+" + to_string(i));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    dfs(0, "");

    cout << "-1\n";

    return 0;
}

 

void dfs(int sum, string s) {
    if (sum == n) {
        if (++cnt == k) {
            cout << s << '\n';
            exit(0);
        }

        return;
    }

    for (int i = 1; i < 4; i++) {
        if (sum == 0)
            dfs(sum + i, s + to_string(i));
        else if (sum + i <= n)
            dfs(sum + i, s + "+" + to_string(i));
    }
}

문제의 답을 찾는 함수이다. 백트래킹으로 합이 n이 되는 1, 2, 3으로 이루어진 식을 구하도록 했다. 이 때 sum으로 만들어진 식의 합을, s에 식을 다음 호출로 보내준다.

이러다 sum이 n과 같아진다면 cnt를 증가시킨다. 이 cnt로 해당 식이 몇 번째 식인지 알 수 있는데, cnt가 k와 같다면 원하는 식을 찾은 것이기에 s를 출력하고, 프로그램을 끝내도록 했다.

 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    dfs(0, "");

    cout << "-1\n";

    return 0;
}

만약 k번째로 오는 식이 없다면 dfs()로 인한 프로그램 종료가 없기에 -1을 출력하게 된다.