[BOJ 2635] 수 이어가기

문제

• BOJ 2635
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

두번째 수는 첫번째 수를 반으로 나눈 후 +1한 값부터 시작한다. 왜냐하면 첫번째수를 반으로 나눈 수를 포함한 전까지는 무조건 네번째 수가 무조건 음수가 나오므로 계산할 필요가 없다. 따라서 첫번째 수를 반으로 나누고 +1한 수부터 시작해서 최대 개수를 구할때 까지 for문을 돌면서 계산한다. 최대 개수일때의 배열도 출력해야 하므로 현재 상황에서 최대 개수인 경우만을 저장해주는 ansArr배열을 만든다. 숫자 몇개를 예로 들어서 직접 손구현을 해보면 어떻게 구현해야 할지 답이 보이는 문제이다.

코드

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.Arrays;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int Ans = 2; //최대 개수
		
		ArrayList<Integer> ansArr = new ArrayList<>();
		
		
		int next = (N / 2) + 1;
		for(int i=next; i<=N; i++) {
			ArrayList<Integer> tmpArr = new ArrayList<>();
			int a = N;
			int b = i;
			tmpArr.add(a);
			tmpArr.add(b);
			int cnt = 2; //첫번째, 두번째는 넣고 시작
			while(a - b >= 0) {
				int tmp = b;
				b = a - b;
				a = tmp;
				cnt++;
				tmpArr.add(b);
			}
			//최대 개수가 점점 증가하다가 줄어드는 경우
			if(cnt < Ans) break;
			if(cnt > Ans) {
				Ans = cnt;
				ansArr = tmpArr;
			}
		}
		bw.write(Ans+"\n");
		for(int i=0; i<ansArr.size(); i++) bw.write(ansArr.get(i)+" ");
		
		bw.flush();
		bw.close();
		br.close();
	}
}