백준 2635 <수 이어가기>

이 문제는 기본적으로 첫 번째 정수를 2로 나눈 것 이상의 수를 두 번째 수로 잡고 전부 계산해보는 문제이다.

 

n을 2로 나눈것 이상을 두 번째 수로 하는 이유는 그렇지 않으면 항상 3번째 오는 수는 2번째 수보다 클 것이고 결과는 3이 나오기 때문이다.

 

예를 들자면 

 

50 25 25 0     50을 2로 나눈수를 두 번째로 가진 경우 

 

50 23 27 결국 50을 2로 나눈수 25 보다 작으면 세 번 재수는 항상 2번째 수보다 크기 때문이다.

 

즉 25 미만의 숫자는 50을 2로 나눈 수부터 시작한것보다 전체 크기가 작다.

 

문제 풀이

1. n/2로 나눈 수 부터 전부 다 돌려본다.
2. ArrayList를 이용해서 ArrayList 크기가 현재 결과 ArrayList 크기보다 크다면 옮겨 담는다.
3. Stringbuilder을 이용해 print 하는 시간을 단축시킨다.

전체 코드

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

public class Main{

	static int max,n;
	static ArrayList<Integer> result;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		for(int i=n/2;i<=n;i++) {
			go(i);
		}
		System.out.println(max);
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<result.size()-1;i++) {
			sb.append(result.get(i));
			sb.append(" ");
		}
		sb.append(result.get(result.size()-1));
		System.out.println(sb);
	}

	private static void go(int i) {
		// TODO Auto-generated method stub
		ArrayList<Integer> a=new ArrayList<Integer>();
		a.add(n);
		a.add(i);
		while(true) {
			int pre=a.get(a.size()-2);
			int now=a.get(a.size()-1);
			if(pre-now>=0) {
				a.add(pre-now);
			}
			else
				break;
		}
		if(max<a.size()) {
			result=new ArrayList<Integer>();
			for(int j=0;j<a.size();j++) {
				result.add(a.get(j));
			}
			max=a.size();
		}
	}
}