[백준/BOJ] 9625 BABBA (Java)

문제

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

9625번: BABBA

버튼이 하나만 있는 기계가 있다.

버튼을 누르면 화면에있는 A가 B로 바뀌고 B는 AB로 바뀐다. 버튼을 K번 눌렀을때, 화면에 표시되어있는 A와 B의 갯수를 출력하는 문제다.

 

---

풀이

다이나믹 프로그래밍 문제다.

버튼을 K번 눌렀을때 A와 B의 갯수를 생각해보자.

 

1. A는 K-1번째 버튼을 눌렀을때, B의 갯수만큼 생성된다.

2. B는 K-1번째 버튼을 눌렀을때, A와 B의 갯수만큼 생성된다.

 

위 논리를 식으로 표햔해보자.

 

dp[1] = 현재 화면에 있는 A의 갯수

dp[2] = 현재 화면에 있는 B의 갯수

 

dp를 계산하기위해 tempDp배열을 만들자.

 

tempDp[1] = 이전 화면에 있는 A의 갯수 

tempDp[2] = 이전 화면에 있는 B의 갯수 + 이전 화면에 있는 A의 갯수

 

최종 식과 코드는 다음과 같다.

tempDp[1] = dp[1]; // dp배열이 업데이트 되지 않았으므로 이전 화면 값이 저장되어있을것이다.

tempDp[2] = dp[1] + dp[2]; // dp배열이 업데이트 되지 않았으므로 이전 화면 값이 저장되어있을것이다.

dp[1] = tempDp[1]; // dp배열을 업데이트 해주자.

dp[2] = tempDp[2];  // dp배열을 업데이트 해주자.

    private void getDp(int cnt){
        if(cnt > K) return;
        tempDp[1] = dp[2];
        tempDp[2] = dp[1]+dp[2];
        dp[1] = tempDp[1];
        dp[2] = tempDp[2];
        getDp(cnt+1);
    }

---

소스코드

https://github.com/devxb/JJUNalgo/blob/master/9625%20BABBA/Main.java#L11

devxb/JJUNalgo