취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2635번 문제인 수 이어가기이다.
문제는 아래 링크를 확인하자.

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

두 번째 수를 첫 번째 수보다 크게 정하면 항상 해당 수에서 수열이 끝나므로, 두 번째 수로 올 수의 후보는 첫 번째 수 이하라는 것을 생각해볼 수 있다.

1 이상 (첫 번째 수) 이하의 각 수를 두 번째 수로 이용해보고, 가장 수열의 길이가 길었던 수를 찾아 문제의 답을 출력하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int func(int x, int y) {
    int temp = x - y;
    if (temp < 0) return 2;
    return func(y, temp) + 1;
}

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

    int N; cin >> N;
    int x = 0, cnt = 0;

    for (int i = 1; i <= N; i++) {
        int temp = func(N, i);
        if (temp > cnt) {
            x = i, cnt = temp;
        }
    }

    cout << cnt << '\n';
    cout << N << ' ' << x;
    while (N - x >= 0) {
        int temp = N - x;
        N = x; x = temp;
        cout << ' ' << x;
    }
}