[Baekjoon] 9625 - BABBA

📝 문제

 

 

 

🔑 풀이 과정

· 문제에 규칙이 다 나와있다. B는 BA로 바뀌고, A는 B로 바뀐다. (알파벳 하나하나를 바꿔주는 것임)

① B가 BA로 바뀌므로, A갯수 = 그 전 B갯수, B 갯수 = 그 전 B갯수이다.

② A가 B로 바뀌므로, B갯수 = 그 전 A갯수이다.

즉, A갯수 = 그 전 B갯수, B 갯수 = 그 전 B갯수 + 그 전 A갯수라는 식이 나온다.

 

· 처음에 실수했던 부분이 첫 화면이 A이고, 그 다음 버튼을 한 번 눌렀을때가 B인데, 한 번 누른것을 A라고 착각했었다.

 

· 그리고 풀고 다른분들 풀이 검색해보니, 다들 그냥 DP 규칙을 찾으셨던데 (i번째일때 i-2 + i-1 인것), 문제에 이미 계산 공식이 나와있으니 굳이 스스로 규칙을 안찾아도 되지 않나...? 라는 생각이 들었다.

 

 

🔓 답안

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));
        StringBuilder sb = new StringBuilder();

        int K = Integer.parseInt(br.readLine()); //버튼을 누르는 횟수

        int[][] arr = new int[K+1][2]; //0번열은 A의 개수, 1번열은 B의 개수

        arr[0][0] = 1;
        arr[0][1] = 0;

        for(int i = 1; i <= K; i++){
            //버튼을 누르기 전의 A개수와 B개수를 가져온다.
            int preA = arr[i-1][0];
            int preB = arr[i-1][1];

            //B가 BA로 바뀌므로, 그 전 B개수만큼 A를 가진다.
            arr[i][0] = preB;
            //B가 BA로 바뀌므로, 그 전 B개수만큼 B를 가진다.
            //A가 B로 바뀌므로, 그 전 A개수만큼 B를 가진다.
            arr[i][1] = preB + preA;
       }

        //출력
        sb.append(arr[K][0]).append(" ").append(arr[K][1]);
        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }

}

 

 

 

🖤 알고리즘 분류

- 다이나믹 프로그래밍