2635번. 수 이어가기

 

아이디어

첫 번째 수를 N, 두 번째 수를 X 라고 할 때 수열은 다음과 같다

 

N, X, N - X, 2X - N, 2N - 3X, ...

 

수열의 길이가 최대가 되기 위해서는 N - X >= 0, 2X - N >= 0, 2N - 3X >= 0, ... 의 조건들을 최대한 많이 만족시킬 수 있는 X 를 선택해야 한다.

 

일단 1번째 조건에 의해서 N >= X 가 되는 범위에서 X 를 선택해야 하는 것을 알 수 있는데 이 때 N 을 선택하면

 

N, N, 0, N

 

으로 길이가 4인 수열을 얻을 수 있다. 모든 입력값 N 에 대해서 최소 4개는 보장이 된다는 뜻이므로 2X - N >= 0 인 범위에 대해서 그 후 조건들을 얼마나 만족시킬 수 있는지를 확인해서 수열의 길이가 최대가 되는 케이스를 출력하면 된다.

 

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int maxCnt = 0;
        List<Integer> result = new ArrayList<>();
        for (int i = N / 2; i <= N; i++) {
            int cnt = 2;

            List<Integer> temp = new ArrayList<>();
            temp.add(N);
            temp.add(i);

            int now = temp.get(cnt - 2) - temp.get(cnt - 1);
            while (now >= 0) {
                cnt++;
                temp.add(now);

                now = temp.get(cnt - 2) - temp.get(cnt - 1);
            }

            if (cnt > maxCnt) {
                maxCnt = cnt;
                result = temp;
            }
        }

        System.out.println(maxCnt);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}