[백준] 자바 9625 BABBA

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게 되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

---

테스트 케이스

 

예제 입력 1

1

예제 출력 1

0 1

예제 입력 2

4

예제 출력 2

2 3

예제 입력 3

10

예제 출력 3

34 55

 

---

접근

모니터 화면에 A가 있는 상태에서 시작해서

누를 때마다 A는 B로 B는 BA로 변환되는 프로그램인데 n번 눌렀을 때 몇 개의 A와 몇개의 B가 있는지 맞추는 문제입니다.

표를 그려서 하나씩 계산해보니 규칙을 쉽게 알 수 있었습니다.

DP	A	B
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5

---

이를 보면 A의 개수는 바로 전의 B의 개수임을 알 수 있고, B의 개수는 이전의 A의 개수와 이전의 B개수의 합임을 알 수  있습니다.

이를 통해 코드를 구현하니 문제가 해결되었습니다.

코드

import java.awt.desktop.SystemEventListener;
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
 	 9625 problem
	*/
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		ArrayList<Integer> a = new ArrayList<>();
		ArrayList<Integer> b = new ArrayList<>();
		a.add(0);
		b.add(1);
		if(num>=2) {
			a.add(1);
			b.add(1);
		}
		if(num>=3) {
			a.add(1);
			b.add(2);
		}
		if(num>=4) {
			for(int i=3; i<num; i++) {
				a.add(b.get(i-1));
				b.add(a.get(i-1) + b.get(i-1));
			}
		}
		bw.write(String.valueOf(a.get(num-1)+" "+b.get(num-1)));
		bw.flush();
		bw.close();
	}
	
}

---

주의