백준 9625 BABBA JAVA 풀이 (DP, 피보나치, O(N))

🔗 문제 링크

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

---

📌 문제 개요

처음 화면에는 A만 1개가 있다.

버튼을 한 번 누를 때마다 A는 B로 바뀌고, B는 BA로 바뀐다.

이렇게 버튼을 K번 눌렀을 때 화면에 존재하는 A와 B의 개수를 구하는 문제

---

📌 접근 방법

처음에는 문자열을 직접 바꿔가며 만들어야 하나 생각할 수 있다.

 

하지만 버튼을 누를수록 문자열 길이가 계속 늘어나기 때문에,

실제 문자열을 생성하는 방식은 비효율적이다.

 

이 문제는 문자열 자체보다 A와 B의 개수 변화 규칙만 보면 훨씬 쉽게 풀 수 있다.

 

• 0번: A → A 1개, B 0개
• 1번: B → A 0개, B 1개
• 2번: BA → A 1개, B 1개
• 3번: BAB → A 1개, B 2개
• 4번: BABBA → A 2개, B 3개

여기서 규칙은 다음과 같다.

• 다음 단계의 A 개수 = 현재 B 개수
• 다음 단계의 B 개수 = 현재 A 개수 + 현재 B 개수

즉, 피보나치 형태의 DP 문제로 볼 수 있다. 여러 풀이에서도 이 문제를 DP 혹은 피보나치 패턴

---

📌 핵심 아이디어

이 문제의 핵심은 문자열을 직접 만들지 않고, A와 B의 개수만 추적하는 것이다.

현재 A의 개수를 A, B의 개수를 B라고 하면 다음 단계는 이렇게 된다.

• nextA = B
• nextB = A + B

초기 상태는 화면에 A만 1개 있으므로

• A = 1
• B = 0

이 상태에서 버튼을 누르는 횟수만큼 반복

---

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int A = 1;
        int B = 0;

        for (int i = 0; i < N; i++) {
            int nextA = B;
            int nextB = A + B;
            A = nextA;
            B = nextB;
        }

        System.out.println(A + " " + B);
    }
}

---

📄 정리

이 문제는 문자열 변환 문제처럼 보이지만, 실제로는 개수 변화 규칙만 찾으면 되는 DP 문제

• 문자열 생성 X
• A, B 개수만 관리
• 점화식은 nextA = B, nextB = A + B
• 피보나치 형태로 반복 처리

시간복잡도는 O(N), 추가 공간은 O(1)이다.