[백준] 9625번 - BABBA [Java]

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

 

[백준] 9625번 - BABBA [Java]

---

1.  아이디어

 

K번 눌렀을 때 A와 B의 개수는 다이나믹 프로그래밍을 활용하면 구할 수 있다.

---

2. 문제풀이

 

버튼을 눌렀을 때, B는 BA로 바뀌고, A는 B로 바뀐다.

이를 식으로 표현하면 버튼을 n번 눌렀을 때 A와 B의 개수를 A(n), B(n)이라고 하면 A(n) = B(n-1), B(n) = B(n-1) + A(n-1) 이 된다.

최초 화면에는 A가 표시되고 있고, 점화식이 나왔으니 다이나믹 프로그래밍으로 풀면 된다.

---

3. 코드

 

import java.io.*;

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

        int K = Integer.parseInt(br.readLine());

        int[] A = new int[1 + K];
        int[] B = new int[1 + K];
        A[0] = 1;

        for (int i = 1; i <= K; i++) {
            B[i] = B[i - 1] + A[i - 1];
            A[i] = B[i - 1];
        }

        sb.append(A[K]).append(" ").append(B[K]);

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기