[BOJ] 백준 2635 수 이어가기 (KOI 2000 초등부)

문제 링크

www.acmicpc.net/problem/2635

2635번: 수 이어가기

 

풀이

규칙이 주어집니다. 그에 따라 구현을 합시다.

두 번째 수로 $N$ 이상의 수를 선택하면 항상 바로 끝나게 되니 $N$ 이하의 모든 수에 대해 돌리면 됩니다.

 

정답 코드

#include <bits/stdc++.h>

#define ft first
#define sd second
#define INF 0x3f3f3f3f
using namespace std;
using vi = vector<int>;

int go(vi &p) {
    int top = (int) p.size() - 1;
    if (p.back() < 0) {
        p.pop_back();
        return top;
    }
    p.push_back(p[top - 1] - p[top]);
    return go(p);
}

int main() {
    int n;
    cin >> n;

    pair<int, vi> ans;
    for (int i = 1; i <= n; i++) {
        vi p(1, n);
        p.push_back(i);
        int val = go(p);
        ans = max(ans, {val, p});
    }
    cout << ans.ft << endl;
    for (int x: ans.sd) {
        cout << x << ' ';
    }
}