[백준] 9625번 : BABBA – JAVA [자바]

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

9625번: BABBA

 

---

• 문제

 

---

• 문제 풀이

백준 9625번 BABBA는 DP (다이나믹 프로그래밍)을 이용해서 푸는 문제이다. DP 이론을 조금 더 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

 

이 문제는 사실 피보나치를 이용해서 푸는 문제이다. 예시를 한 번 보겠다.

처음 기계의 시작 화면은 A로 시작하고 버튼을 누르면 A는 B로, B는 BA로 바뀐다.

 

버튼 1번을 누르면 B가 되고 버튼을 또 한번 누르면 BA가 된다.

즉 k = 1이면 A = 0, B = 1이고 k = 2이면 A = 1, B = 1이 된다.

 

버튼을 또 한 번 누르면 BAB가 돼서 k = 3이면 A = 1, B= 2가 된다. 이거를 계속하면 피보나치 수열과 같다는 것을 찾을 수 있다.

 

---

• 코드

 

import java.util.*;
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.print(dp[0][k] + " " + dp[1][k]);
    }
}

 

---

• 후기

되게 기본적인 1차원 배열을 이용한 DP 였던 거 같다.