[6590] 덧셈 체인

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

6590번: 덧셈 체인

<문제>

처음엔 2진수 비슷하게 접근했는데, 4번 조건이 두 자연수가 아닌 임의의 자연수의 합이라면 올바른 접근이긴 하다.

다만, 중복을 포함하여 2개를 선택해야 하므로, 2진수나 비트적인 접근이 불가능한것으로 보인다.

n이 100이라서 브루트포스가 제대로 돌아가기 힘든것처럼 보였지만, 가지치기를 잘 해주면 괜찮다.

현재 상태에서 갈수있는 다음 상태를 getNextNumber()를 통해, bool[1]~bool[n]에 표시해주고

마지막으로 선택한 숫자가 S라고 할때 [S+1, 2 * S)의 범위중 bool[]이 true인것만 재귀적으로 탐색한다.

테스트케이스형 문제이고, 매 상태마다 다시 bool[]을 재구성해야하는 점에 유의할 필요가 있고..

현재로서의 정답의 수열의 길이를 이용해서, (현재 수열의 길이)>(정답 수열의 길이)이거나

(현재 수열의 길이)==(정답 수열의 길이)&&(현재 수열이 아직 완성되지 않은 경우)에 가지치기가 가능하다.

 

 

vector<int> ans : 정답 수열

vector<int> cur : 현재 수열, 재귀적인 탐색에서 하나의 상태

int ansSize : 정답 수열의 길이, 가지치기의 기준

bool nextNumber[] : 매 상태마다 초기화&&재구성하는, cur[i]+cur[j]로 만들 수 있는 자연수 (가능한 다음 상태)

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, ansSize;
bool nextNumber[105];
vector<int> ans, cur;
void getNextNumber(void) {
    int S = cur.size();
    for (int i = 0; i < S; i++)
        if (cur[i] + cur[i] <= n) nextNumber[cur[i] + cur[i]] = true;
    for (int i = 0; i < S; i++)
        for (int j = i + 1; j < S; j++)
            if (cur[i] + cur[j] <= n) nextNumber[cur[i] + cur[j]] = true;
}
void f(void) {
    if (cur.size() > ansSize) return;
    if (cur.back() == n) {
        if (ans.empty() || cur.size() < ansSize) {
            ansSize = cur.size();
            ans.clear();
            ans = cur;
        }
        return;
    }
    if (cur.size() == ans.size()) return;
    int S = cur.back();
    memset(nextNumber, 0, sizeof(nextNumber));
    getNextNumber();
    for (int i = 2 * S; i > S; i--) {
        if (i <= n && nextNumber[i] == true) {
            cur.push_back(i);
            f();
            cur.pop_back();
        }
    }
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (;;) {
        cin >> n;
        if (n == 0) break;
        ans.clear();
        cur.clear();
        cur.push_back(1);
        ansSize = 10000;
        memset(nextNumber, 0, sizeof(nextNumber));
        f();
        for (auto& i : ans) cout << i << " ";
        cout << '\n';
    }
    return 0;
}