BOJ 2635번: 수 이어가기

문제

다음과 같은 규칙에 따라 수들을 만들려고 한다.

첫 번째 수로 양의 정수가 주어진다.
두 번째 수는 양의 정수 중에서 하나를 선택한다.
세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.
첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

입력

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

출력

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

---

문제 풀이 1 - 성공

처음에는 배열을 만들어서 숫자들을 저장해놨다가 최대 개수의 수들을 출력하는 방법을 생각했었다. 그러나 각 경우마다 숫자의 개수가 다르고 숫자들을 일일이 다 저장하는 것은 너무 비효율적인 것 같아서 다른 방법을 찾아보게되었다.

최대 개수일 경우의 두번째 숫자만 저장해놓고 출력 단계에서 그 수들을 다시 계산해 바로 출력하는 방법으로 풀었다.

1. numcnt() 함수를 따로 구현해 재귀로 숫자의 개수를 구한다.
2. 최대 개수일 때의 두 번째 숫자를 따로 저장해놓고 출력 단계에서 수들을 계산해 출력한다.

#include <iostream>
using namespace std;

int numcnt(int prev, int num) {
    int next = prev - num;
    if(next < 0) return 2; // 2번째 수까지
    return numcnt(num, next) + 1;
}

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

    int n, i, sec, count, max = 0, answer;
    cin >> n;

    for(i = 1; i <= n; i++) {
        count = numcnt(n, i);
        
        if(count > max) {
            max = count;
            sec = i;
        }
    }
    
    cout << max << '\n';
    cout << n << " " << sec;
    
    int temp = n - sec;
    while(temp >= 0) {
        n = sec;
        sec = temp;
        cout << " " << sec;
        temp = n - sec;
    }

    return 0;
}