BOJ_9625 : BABBA

👉 문제링크

9625번: BABBA

---

---

🔸 문제 분석 🔸

• A에서 시작해서 버튼을 누를 때 마다 다음과 같은 규칙이 반복 된다.
  • 모든 A는 B로 바뀐다.
  • 모든 B는 BA로 바뀐다.
• k번 눌렀을때 A와 B의 개수를 출력한다.
• AB의 개수가 피보나치 수열 방식으로 증가한다.
  • k = 0, 1 0
  • k = 1, 1 1
  • k = 2, 1 2
  • k = 3, 2 3
• dp 리스트로 보면 : 1 0 1 1 2 3 ..

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int[] dp = new int[k+2];

        dp[0] = 1;
        dp[1] = 0;

        for (int i = 2; i <= k+1; i++) {
            dp[i] = dp[i-2] + dp[i-1];
        }
        System.out.println(dp[k] + " " + dp[k+1]);
    }
}

🔸 코드 해석 🔸

• k의 수만큼 dp 리스트의 크기를 할당한다.
• a b의 상태를 dp 리스트에 저장하며 계산한다.

---

🔸 end 🔸

• 피보나치 수열과 같다고 생각하니 쉽게 풀렸다.