[BOJ] 2635 수 이어가기 - JAVA

1. 문제

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

2635번: 수 이어가기

1. 첫번째 수로 양의 정수가 주어진다.
2. 두번째 수는 임의로 정한다.
3. 세번째 수부터 모든 수는 2번째 전 수-1번째 전 수를 뺀 값이다.
4. 음의 정수가 만들어지면 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

* 문제에서 얘기하는 양의 정수는 0을 포함한다.

---

2. 풀이

1. 첫번째 수는 항상 N, 두번째 수는 0부터 N까지 가능하다.
2. first, second 수를 변경해가면서 카운트를 센다. 만약 first-second<0이라면 그 수열체크는 끝난다. 해당 수열의 길이(cnt)와 저장해둔 maxLen과 비교해서 다시 담는다.
3. 마지막에는 저장된 maxSecond로 다시 수열을 만들면서 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_2635_수이어가기 {
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());

        int maxLen = 1;
        int maxSecond = N;

        int first, second;
        for (int num = N; num >= 0; num--) {
            first = N;
            second = num;
            int cnt = 2;

            while (first - second >= 0) {
                int third = first - second;
                first = second;
                second = third;
                cnt++;
            }

            if (maxLen < cnt) {
                maxLen = cnt;
                maxSecond = num;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(maxLen).append("\n");
        sb.append(N).append(" ").append(maxSecond).append(" ");

        first = N;
        while (first - maxSecond >= 0) {
            int third = first - maxSecond;
            first = maxSecond;
            maxSecond = third;

            sb.append(maxSecond).append(" ");
        }

        System.out.println(sb);
    }
}

---

3. 결과

양의 정수라면서 왜 0이 포함되는지 몰라서 한 번 틀렸다.

그리고 0이 포함되면서 자연스럽게 두 번째 숫자도 첫번째 숫자와 동일할 수 있게 됐다. 그래서 또 틀렸다.

고등수학까지는 0이 양의 정수에 포함안됐는데 그 뒤에 바뀌었나싶다.