[알고리즘 문제풀이] 백준 9625번 - BABBA

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

풀이

첫 글자는 A로 시작합니다. 그리고 버튼을 한 번씩 누를 때 마다, 모든 A는 B로 바뀌고, 모든 B는 BA로 바뀌게 됩니다.

1) A -> B
2) B -> BA
위 두 작업은 순차적으로 수행되는 것이 아니고, 병렬적으로 수행됩니다. 코드는 순차적으로 작성하긴 해야하는데 병렬적으로 수행되도록 구현하려면, 다음 상태 (A', B'라고 칭함) 변수를 지정하면 됩니다.

1) A -> B'
2) B -> B'A'
위와 같이 표현하면 이전 A, B값이 서로 영향을 주지 않고 다음 값을 나타낼 수 있게됩니다.

예시

ABA -> B'B'A'B' (BBAB)

• 버튼 누르기 전 : A(2개), B(1개)
• 버튼 누른 후 : A(1개), B(3개)

위와 같은 식으로 버튼을 누른 후 A와 B의 개수를 구하면 됩니다.

소스코드

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));
        int k = Integer.parseInt(br.readLine());
        int a = 1;
        int b = 0;
        for(int i = 0; i < k; i++){
            int tb = a + b;
            int ta = b;

            a = ta;
            b = tb;
        }
        bw.write(a+" "+b);
        bw.flush();
        bw.close();
        br.close();
    }
}