백준 2635 수 이어가기

문제

설명

너무 단순하게 풀면 시간초과가 나올 것 같아서 시도하지 못하다가 

방법이 떠오르지 않아서 생각하는대로 구현해보았다.

 

생각한 방법은 1부터 주어진 숫자까지 모두 구하는 방법이었다. 

그래서 for문을 통해서 시작하는 숫자를 i로 두고, 재귀를 통해서 끝까지 구해주었다. 

결과에 배열을 출력해야 하기 때문에 list 객체를 넘겨서 조건이 맞으면 계속 add를 해주었고 

size가 가장 큰 배열인지 체크해주었다. 

 

느릴줄 알았는데 속도는 생각보다 빠르게 156ms로 나왔다.

더 효율적인 방법이 있을까 싶어서 검색해보았지만 딱히 찾지 못했다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    // 2635 수 이어가기
    public static void main(String[] args) throws IOException {
        process();
    }

    private static void process() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int num = Integer.parseInt(br.readLine());
        int maxSize = -1;
        List<Integer> maxList = Collections.emptyList();
        List<Integer> tempList;

        for (int i = 1; i <= num; i++) {
            // list 객체를 만들어서 재귀 진행
            tempList = new ArrayList<>();
            tempList.add(num);
            getTempListSizeRecursive(num, i, tempList);
            final int tempListSize = tempList.size();
            if(maxSize < tempListSize) {
                maxSize = tempListSize;
                maxList = tempList;
            }
        }

        final int maxListSize = maxList.size();
        bw.write(maxListSize+ "\n");
        for (int i = 0; i < maxListSize; i++) {
            bw.write(maxList.get(i) + " ");
        }
        bw.flush();
        bw.close();
    }

    private static void getTempListSizeRecursive(int prevNum, int nextNum, List<Integer> list) {
        // 앞에수에서 뒤에수를 뺀 값을 구함.
        int subtract = prevNum - nextNum;
        list.add(nextNum);
        if (subtract >= 0) {
            getTempListSizeRecursive(nextNum, subtract, list);
        } else {
            // 뺸 값이 0 미만(음수)이면 재귀 종료
        }
    }
}