[백준 알고리즘] 백준 2635번 수 이어가기 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 2635번 수 이어가기 자바(Java)

1) 문제번호 : 2635번

 

2) 문제 출처

www.acmicpc.net/problem/2635

2635번: 수 이어가기

 

2. 문제

다음과 같은 규칙에 따라 수들을 만들려고 한다.

1. 첫 번째 수로 양의 정수가 주어진다.
2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.
3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

 

3. 제약사항

- 

4. 입력

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

5. 출력

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

 

6. 풀이

- i는 100부터 반복문을 돌리면 되는데, 50까지 돌리면 결국엔 계속 count는 4가 나온다. 예를 들어, 100, 100, 0, 100/ 100, 50, 0, 100 이렇게 나온다.

- 그렇기 떄문에 N/2를 해줘서 반복문을 돌려주고 i-2 번째에서 i-1번째 값을 빼줘서 i번째에 넣는다.

 

 

 

7. 소스 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 수
		int count = 0; // 리스트 최대 크기 저장
		
		//리스트 결과 저장 배열
		ArrayList<Integer> result = new ArrayList<>();
		
		//N/2를 안하면 계속 100에서 걸려서 count가 4가 나온다.
		for(int i=N;i>=N/2;i--) {
			ArrayList<Integer> List = new ArrayList<>();
			List.add(N);
			
			int temp = N;
			int temp2 = i;
			
			while(true) {
				//음수면 종료
				if(temp<0) break;
				
				int temp3 = temp;
				//2번째 숫자가 0보다 크거나 같으면 리스트에 넣기
				if(temp2>=0) List.add(temp2);
				
				//n-2번째에서 n-1번째 값 빼기
				temp = temp2;
				temp2 = temp3 - temp;
			}
			
			if(count<List.size()) {
				count = List.size();
				result = List;
			}
		}
		System.out.println(count);
		for(Integer c : result) System.out.print(c +" ");
	}
}

---