[C++] 수들의 합 6 (백준 1821번)

https://www.acmicpc.net/problem/1821

 

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

vector<int> fact;
vector<int> ans;
vector<int> mul;
vector<bool> chk;

int n, f;
bool fin = false;

void dfs(int idx, int res) {
    if (fin || res > f) {
        return;
    }
    if (idx == n) {
        if (res == f) {
            for (int x: ans) {
                cout << x << ' ';
            }
            cout << '\n';
            fin = true;
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!chk[i]) {
            chk[i] = true;
            ans[idx] = i;
            dfs(idx + 1, res + mul[idx] * i);
            if (fin) break;
            chk[i] = false;
        }
    }
}

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

    cin >> n >> f;
    fact = vector<int>(n, 1);
    ans = vector<int>(n);
    mul = vector<int>(n);
    chk = vector<bool>(n + 1);

    int tmp = 1;
    for (int i = 1; i < n; i++) {
        tmp *= i;
        fact[i] = tmp;
    }

    for (int i = 0; i < n; i++) {
        mul[i] = fact[n - 1] / fact[i] / fact[n - 1 - i];
    }

    dfs(0, 0);
}

n의 크기가 작아서 백트래킹 방식으로 풀었다. (정답)

 

여기서 promising 체크는 chk 배열을 통해 하였다. chk[i]는 i번째 수가 이전에 사용되었는지에 대한 정보이다.

 

규칙을 찾는 과정

 

[참고] https://janghan-kor.tistory.com/784