[C++] 백준 2635 - 수 이어가기

문제 - 수 이어가기 (Silver 5)

[백준 2635] https://www.acmicpc.net/problem/2635

풀이 전략

• 처음에는 입력한 N 값의 다음 수가 무작위 수이기 때문에 random 함수를 사용해야 하나 고민을 했었다. 하지만, 구하고자 하는 것은 최대 개수이기 때문에 전체 수의 경우의수를 비교해서 제일 큰 값을 찾으면 되서 random 함수를 사용하지 않아도 된다는 것을 깨달았다.
• 임의의 배열에 경우의 수를 저장하다가 최대가 되는 경우의 수 일 때 Main 배열에 복사를 하고 그 배열을 구성하는 요소 개수와 모든 요소들을 출력

소스 코드

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

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

    int N;
    cin>>N;
    vector<int> A;

    for(int i=1;i<=N;i++){
        vector<int> tmp; // 최대 경우의 수를 찾기 위해 숫자들을 임시로 저장할 tmp 생성
        tmp.push_back(N); // 입력 값을 저장
        tmp.push_back(i); // 입력 값의 다음 값을 저장
        for(int j=1;;j++){
            if(tmp[j-1]<tmp[j]){
                break;
            } 
            // 현재 숫자가 이전 숫자보다 크면 (Next 숫자가 음수가 되기 때문) 반복문 탈출
            tmp.push_back(tmp[j-1]-tmp[j]); 
            // 반복문 탈출하기 전까지 계속 이전 숫자에서 현재 숫자를 뺀 수를 저장
        }
        if(tmp.size()>A.size()){
            A=tmp;
        }
        // tmp에 저장된 숫자의 개수가 최대가 되면 A에 복사
    }
    cout<<A.size()<<'\n'; // 최대 갯수가 들어 있는 A의 원소 개수 출력
    for(auto V: A){
        cout<<V<<" ";
    } // A안에 있는 원소 출력
    cout<<'\n';
    return 0;
}

결과

결론

Random 함수를 사용하지 않고 임시 배열에 저장했다가 최대일 때 메인 배열에 복사하는 방식으로도 최대값을 구할 수 있다.