백준 9625번 : BABBA

 

화면을 누를 때마다 화면에 있는 A는 B로, B는 BA로 변한다.

 

화면 :         A       -> BA      -> BAB    -> BABBA -> ...

(A B) :      (1 0)        (1 1 )         (1 2 )        (2 3)   

 

A 는 B로, B는 BA로 변하는데 이걸 다시 풀어보면, 

한번 버튼을 누를 때마다 A는 현재 B의 개수가 되고, B는 현재 A 개수 + 현재 B의 개수가 됨을 알 수 있다.

 

N번만큼 눌렀을 때

N번째 A는 N-1번째의 B의 개수가, N번째 B는 N-1 번째의 A 개수 + N-1 번째의 B 개수가 될 수 있다.

즉, B = (N-1 번째의 A 개수) + (N-1 번째의 B 개수) =  (N-2 번째의 B의 개수) + (N- 1번째의 B의 개수)가 된다.

 

결국, 이 문제는 피보나치 수열의 문제였다.

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N = sc.nextInt();
		int arr[] = new int[N+1];
		
		arr[0] = 0;
		arr[1] = 1;
		for(int i=2;i<=N;i++) {
			arr[i] = arr[i-1]+arr[i-2];
		}
		
		System.out.println(arr[N-1]+" "+arr[N]);
	}
}

피보나치 수열이란 0,1,1,2,3,5,8,13,... 등, N번째 수는 N-1번째 수 + N-2번째 수가 되는 수열을 의미한다.

0번째는 0, 1번째는 1로 항상 고정되어 있기 때문에 두 값만 정의하고 for문을 통해 계속 값을 N까지 더해가면서 값을 얻어내면 된다.

 

 

N번째 A = (N-1번째의 B개수)

N번째 B = (N-1 번째의 A 개수) + (N-1 번째의 B 개수) =  (N-2 번째의 B의 개수) + (N- 1번째의 B의 개수)

 

로 정의 내릴 수 있기 때문에, A는 arr[N-1]의 값을, B는 arr[N]의 값을 출력하면 된다.

 

 

문제가 규칙성이 있어서 규칙만 파악하면 되는 문제였다. 더 효율적으로 문제를 풀기 위해서는 배열을 사용하지 않아도 된다. 

지나간 숫자를 다시 사용하지 않고 계속 갱신하기 때문에

배열이 아니라 x,y,z 딱 3 변수만 사용한다면 공간을 조금 더 효율적으로 사용할 수 있다.