[자바]백준 9625번 BABBA [다이나믹프로그래밍][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게 되었다. 버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

예제

예제 사진

알고리즘 분류

• 다이나믹 프로그래밍

문제 설명

처음에 A라는 글자가 있는데 버튼을 누르면 B가 되고 한 번 더 누르면 BA가 된다.

이 말은 아래와 같다.

• A => B
• B => BA

즉 A는 B로 변환하고 B는 BA로 변환하는데, 이때 K번 누르면 A와 B의 개수를 출력하는 문제다.

해설

문제를 보면 A는 B가 되고 B는 BA가 생기는데 사실 BA든 AB든 상관이 없다. 그냥 A와 B의 개수만 알면 된다.

그럼 다시 생각해 보자, A는 버튼을 누르면 A는 0개 B는 1개가 되고, B는 버튼을 누르면 A는 1개 B는 1개가 되는 것이다.

그러면 K - 1번 눌렀을때 A와 B의 개수를 알면, K번의 A와 B의 개수를 알 수 있다.

K번의 A의 개수는 K - 1번의 B의 개수가 되며,
K번의 B의 개수는 K - 1번의 B의 개수 + K - 1번의 A의 개수가 된다.

그렇다면 0번부터 순서대로 A와 B의 개수를 파악하다 보면 K번의 A와 B의 개수를 알 수 있게 된다.

즉, 다이내믹 프로그래밍(dp, 동적계획법)을 사용하면 쉽게 풀 수 있는 문제이다.

 

코드

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

        int K = Integer.parseInt(br.readLine());
        
        int[][] arr = new int[K + 1][2];
        arr[0][0] = 1;

        for (int i = 0; i < arr.length - 1; i++) {
            arr[i + 1][0] = arr[i][1];
            arr[i + 1][1] = arr[i][0] + arr[i][1];
        }
        
        bw.write(arr[K][0] + " " + arr[K][1]);
        bw.flush();
        bw.close();
        br.close();
    }
}

우선 A와 B의 개수를 담을 이중 배열 arr을 만들어주고 열의 길이는 K 보다 하나 더 긴 K + 1로 잡아줘야 한다.

0번 ~ K번의 기록을 갖고 있어야 하므로 길이는 K + 1이 된다.

 

그리고 처음 시작 A 1개를 초기화해주고 위에 작성한 해설 규칙대로 코드를 작성해 주면 된다.