#9625 : BABBA

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

 

2022.03.14

버튼을 k번 눌렀을 때의 결과값은 k-1번 눌렀을 때의 결과값을 이용하여 구해야 한다.

k-1번 눌렀을 때의 결과값은 또다시 k-2번 눌렀을 때의 결과값을 이용하여 구해야 한다.

...

결국 1번 눌렀을 때의 결과값부터 모두 살펴야 한다.

이걸 매번 반복했다가는 시간초과가 난다. 즉, 가능한 답을 미리 구해놓고 출력 시에 꺼내오는 방식으로 풀어야 한다.

따라서 다이나믹 프로그래밍을 쓰기에 매우 적합한 문제이다.

 

주어지는 k의 최댓값은 45이다.

45번의 반복문을 돌려, 버튼을 1번, 2번, ... , 45번 누를 때의 A와 B의 개수를 모두 미리 구해서 배열에 저장해놓고,

k값에 맞게 그 배열에서 정답을 꺼내오면 된다.

 

코드

Java(2022.03.14)

import java.util.Scanner;

public class Main {
	
	static int k;	//버튼을 누르는 횟수
	static int[] a;	//버튼을 누르는 횟수당 a의 개수
	static int[] b;	//버튼을 누르는 횟수당 b의 개수
	
	//버튼을 누르기 전 상태를 참고하여 버튼을 누른 후의 A/B개수를 계산하는 함수
	static void dp(int cur) {
		//버튼을 누르기 전 A와 B의 개수 찾아오기
		int prev_a = a[cur-1];
		int prev_b = b[cur-1];
		
		//A는 모두 B로 변함 -> prev_a만큼 B 개수를 더하기
		b[cur] += prev_a;
		//B는 모두 BA로 변함 -> prev_b만큼 B와 A 개수를 더하기
		a[cur] += prev_b;
		b[cur] += prev_b;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//a와 b의 n번 인덱스에는 n번 눌렀을 때 A/B의 개수 저장. 최대 45번 누르므로 크기가 46인 배열로 선언.
		a = new int[46];
		b = new int[46];
		a[0] = 1;	//버튼을 한 번도 안 누른 상태에서는 A가 한 개.
		Scanner sc = new Scanner(System.in);
		//k 읽어오기
		k = sc.nextInt();
		
		//a와 b에 미리 값을 저장해두기
		for(int i = 1; i<46; i++) dp(i);
		
		System.out.print(a[k] + " " + b[k]);
		
		sc.close();
	}

}