백준 9625: BABBA[JAVA]

[문제 링크]

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

[난이도]

- Silver 5

 

[알고리즘]

- DP

 

[코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int K = Integer.parseInt(br.readLine());

        // dp 배열 정의
        int[] dpA = new int[K + 1]; // K + 1인 이유 0번 눌렀을 때 부터 K번 눌렀을 때 까지의 상태를 저장하기 위함
        int[] dpB = new int[K + 1];

        // 초기값 설정
        dpA[0] = 1;
        dpB[0] = 0;

        // dp 배열 채우기
        for (int i = 1; i <= K; i++) {
            dpA[i] = dpB[i-1];
            dpB[i] = dpA[i - 1] + dpB[i - 1];
        }

        System.out.println(dpA[K] + " " + dpB[K]);
    }
}

[풀이]

 

1. 문제 이해 및 분석
버튼을 누를때 마다 a는 b로 b는 ba로 바뀜. 0번 눌렀을 때 부터 K번 누를때 까지 를 체크해야하므로 bottom-up방식을 사용

2.DP 배열 정의
dpA[i] 는 버튼을 i번 눌렀을 때 화면에 있는 a의 개수
dpB[i] 는 버튼을 i번 눌렀을 때 화면에 있는 b의 개수

3.초기값 설정
dpA[0] = 1
dpB[0] = 0

4. 점화식 작성
dpA[i] = dpB[i-1] : 이전 단계의 b가 현재단계의 a로 바뀜
dpB[i] = dpA[i-1] + dpB[i-1] + dpB[i-1] : 이전단계의 a가 b로 바뀌고, 이전 단계의 b는 ba로 바뀜

5.DP 배열 채우기
1부터 K까지의 모든 단계를 차례로 계산해 dp배열을 채움

6.최종 결과 출력
버튼을 k번 눌렀을 때 a와 b의 개수 출력