[백준/java] 9625번:BABBA - DP(Dynamic Programming)

문제

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

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

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

입력

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

출력

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

 

 

문제풀이 도출과정

 

728x90

 

처음엔 진짜 있는 그대로 풀었다.

 

"A"가 나오면 "B"로 바꿔주고, "B"가 나오면 "BA"로 바꿔줬다.

 

package dynamicProgramming;

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

public class BABBA {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] cnt = new int[2];
		int K = Integer.parseInt(br.readLine());
		String[] arr = new String[46];
		
		arr[0] = "A"; arr[1] = "B"; arr[2] = "BA";
		for (int i = 3; i < K+1; i++) {
			String temp = "";
			String[] tempArr = arr[i-1].split("");
			
			for (int j = 0; j < tempArr.length; j++) {
				if("A".equals(tempArr[j])) temp += "B";
				else if("B".equals(tempArr[j])) temp += "BA";
			}
			
			arr[i] = temp;
			System.out.println("temp : " + temp);
		}
		
		for (int i = 0; i < arr[K].length(); i++) {
			if('A' == arr[K].charAt(i)) cnt[0]++;
			else cnt[1]++;
		}

		System.out.println(cnt[0] + " " + cnt[1]);
	}
}

 

그러고서는 A와 B의 갯수를 샜는데,

A와 B가 수도없이 증가하면서 프로그램은 통제가 불가능해졌다.

 

이건 아니다 싶었다.

 

생각해보니 A와 B의 패턴이 보이는거같기도 했다.

 

백준 9625번: BABBA 답안 도출과정

4번째와 5번째 패턴이 뒤에 가면 갈수록 이어 붙는 모양이었다.

 

일정하게 늘어나는 패턴을 발견했으니 A와 B의 증가 패턴도 있겠다 싶었다.

 

백준 9625번: BABBA 답안 도출과정

역시나..

 

A와 B의 갯수는 각각의 피보나치 수열이 있었던 것이다.

 

A보다 B의 패턴이 한 차수 더 빠르게 나타나는 패턴이다.

 

B는 완전히 피보나치 수열 패턴을 띄고

A는 한 차수씩 뒤로 밀린 패턴이다.

 

어쨌든 간에 K == 2인 상황부터는 피보나치 수열과 똑같이 흘러가는 모습이다.

 

백준 9625번: BABBA 답안 도출과정

 

package dynamicProgramming;

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

public class BABBA {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		int[][] arr = new int[46][2];
		arr[0][0] = 1; arr[0][1] = 0;
		arr[1][0] = 0; arr[1][1] = 1;
		
		for (int i = 2; i < arr.length; i++) {
			arr[i][0] = arr[i-1][0] + arr[i-2][0];
			arr[i][1] = arr[i-1][1] + arr[i-2][1];
		}
		
		System.out.println(arr[K][0] + " " + arr[K][1]);
	}
}

 

결과는....