[Java][백준] 9625번 BABBA

9625번: BABBA

---

 

아이디어

버튼 1번을 누르면 B가 되고 버튼을 또 한번 누르면 BA가 된다. 즉, k = 1이면 A = 0, B = 1이고 k = 2이면 A = 1, B = 1이 된다. 표로 나타내면 다음과 같다.

k	1	2	3	4	5	6	7	8	9
A	0	1	1	2	3	5	8	13	21
B	1	1	2	3	5	8	13	21	34

 

이 문제는 사실 피보나치 수열을 이용하는 문제라는 것을 알 수 있다. DP로 풀자.

 

전체 코드

import java.util.*;
import java.io.*;

public class BJ_9625 {
    public static void main(String[] args) throws IOException {
    	// BABBA
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        
        int[][] dp = new int[2][46];
        dp[0][2] = dp[1][1] = dp[1][2] = 1;
        for (int i = 3; i <= k; i++) {
            dp[0][i] = dp[0][i-2] + dp[0][i-1];
            dp[1][i] = dp[1][i-2] + dp[1][i-1];
        }
        System.out.print(dp[0][k] + " " + dp[1][k]);
    }
}

 

dp[0][i]는 i번째에 따른 A의 개수

dp[1][i]는 i번째에 따른 B의 개수를 의미한다.

 

코드에 대한 설명은 크게 어렵지 않으니 생략하도록 하겠다. 풀이 방식은 피보나치 수열에 대한 dp문제와 같았다.