[백준 자바JAVA] 9625번 - BABBA

https://www.acmicpc.net/problem/9625

---

● 문제

초기상태는 A 1번 눌렀을땐 B 2번 눌렀을 땐 BA 3번 눌렀을땐 BAB 4번 눌렀을땐 BABBA.....

이는 화면에 A는 B로 바뀌고 B는 BA로 바뀐다는 걸 알 수 있다. 각 A,B의 횟수를 표로 나타낸다면

클릭수(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.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int K = Integer.parseInt(br.readLine());
        int[][] dp = new int[2][46];

        dp[0][2] = 1;
        dp[1][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.println(dp[0][K] + " " + dp[1][K]);
    }
}

 

---