[백준] 9625 - BABBA

1. 문제

9625번: BABBA

2. 개요

한 버튼이 있다. 버튼을 누르면 모든 A는 B로 변하고 모든 B는 BA로 변한다.

초기에 A가 표시되어있을 때 버튼을 K번 눌렀을 경우 A, B 각각의 개수를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

버튼을 1회 누르면 B로 (0, 1).

2회 누르면 BA로 (1, 1) 이 된다.

3회째 누르게 되면 BAB로 (1, 2)가 되며 4회째에는 BABBA로 (2, 3)이 된다.

계속해서 반복해나가면 피보나치 수열의 모습을 볼 수 있다.

따라서 dp테이블에 피보나치 수열을 넣어두고 이 테이블에서 값을 빼내온다.

3-2. Python

import sys

K = int(sys.stdin.readline())

dp = [0 for i in range(46)]

dp[1], dp[2] = 1, 1

for i in range(3, 46):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[K - 1], dp[K])

3-3. C#

namespace boj_9625
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int K = int.Parse(Console.ReadLine());

            int[] dp = new int[46];
            dp[1] = 1;
            dp[2] = 1;

            for (int i = 3; i < 46; i++)
                dp[i] = dp[i - 1] + dp[i - 2];

            Console.WriteLine($"{dp[K - 1]} {dp[K]}");
        }
    }
}