BABBA - 9625

문제

풀이

import java.util.Scanner;

// BABBA - S5 - DP
public class ex9652 {

    static int n;
    static int[][] dp = new int[2][46];
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);

        n = sc.nextInt();
        // 규칙 : A -> B , B -> AB
        // 0 -> A
        // 1 -> B
        // 2 -> BA
        // 3 -> BAB
        // 4 -> BABBA
        // 5 -> BABBABAB

        // [0][n] : A
        // [1][n] : B

        // 한번 눌렀을때 - B 1개
        dp[1][1] = 1;
        // 두번 눌렀을때 - A,B 각 1개
        dp[0][2] = 1;
        dp[1][2] = 1;

        for(int i=3; i<dp[0].length; 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.println(dp[0][n] + " " + dp[1][n]);
    }
}

DP 문제다. 계속 반복된다. -> DP
문제에서 한번 클릭하면 A->B로 B->BA로 된다고 한다.

테이블을 만들어 기본값을 정의하고 식을 찾아보자.

0 -> A
1 -> B
2 -> BA
3 -> BAB
4 -> BABBA
5 -> BABBABAB

이렇게 된다. 우선 A의 수를 dp[0][n] , B를 dp[1][n]이라고 하자.

한번 눌렀을 때 A,B의 수는 dp[0][1] = 0; dp[1][1] = 1; 이 된다.
두번 눌렀을 때 A,B의 수는 dp[0][2] = 1; dp[1][2] = 1; 이 된다.
세번 눌렀을 때 A,B의 수는 dp[0][3] = 1; dp[1][3] = 2; 이 된다.

위의 패턴을 보면 A와 B는 dp[0][i-2] + dp[0][i-3] / dp[1][i-2] + dp[1][i-3] 이런 패턴을 가지는 것을 확인 가능하다.