(C++) - 백준(BOJ) 2635 : 수 이어가기

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

2635번: 수 이어가기

brute force로 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

첫 번째 수 n, 가장 긴 수열의 길이 maxLength, 그 때의 수를 저장할 vector형 nums를 선언하고 n에 입력을 받습니다.

📔 풀이과정

두 번째 수는 선택할 양의 정수이므로 1 ~ n까지의 범위가 선택 가능합니다. n이 넘어가면 바로 세 번째 수가 음수가 되기 때문에 확인할 필요가 없습니다.

1. 1 ~ n만큼 for loop를 수행하며 두 번째 수를 지역변수 secondNum을 선언해 저장합니다.

  1-1. 세 번째 수는 지역변수 nextNum를 선언해 n - secondNum값을 저장합니다.

  1-2. 세 번째 수는 음수가 아니며 유효하므로 수열의 최소 길이는 3입니다. 이를 지역변수 length를 선언해 저장합니다.

  1-3. vector v를 선언해 n, secondNum, nextNum를 저장합니다.

2. while loop를 수행합니다.

  2-1. 이제 수를 nextNum이 음수일 때까지 계속 이어 가며 v에 원소를 저장하고 길이 length를 늘려줍니다.

3. loop 탈출 후 maxLength와 length를 비교해 이번 수열 길이가 더 길다면 정답이 될 수 있으므로 nums, maxLength를 갱신합니다.

📔 정답출력

maxLength와 nums의 원소들을 형식에 맞게 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, maxLength;
vector <int> nums;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        int secondNum = i;
        int nextNum = n - secondNum;
        int length = 3;
        vector<int> v = {n, secondNum, nextNum};

        while(1){
            int tmp = nextNum;
            nextNum = secondNum - nextNum;
            if(nextNum < 0) break;
            secondNum = tmp;
            length++;
            v.push_back(nextNum);
        }

        if(maxLength < length) nums = v, maxLength = length;
    }
    cout << maxLength << '\n';
    for(auto e : nums) cout << e << ' ';
}