[Java] 백준 풀기 9625 - BABBA

자바 백준 9625번

실버 5

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

9625번: BABBA

 

 

 

 

 

문제 보기

분류: 다이나믹 프로그래밍

 

 

 

 

 

문제 풀기

버튼을 눌렀을때 다음에 나타날 A의 개수는 이전의 B의 개수와 같다.

B -> BA

버튼을 눌렀을때 다음에 나타날 B의 개수는 이전의 A와  B의 개수와 같다.

A -> B, B -> BA

 

K번째 버튼을 누를때까지 count를 저장할 k+1 개의 array를 생성한다.버튼을 한번 눌렀을때의 값을 aCount[1] = 0 과 bCount[1] = 1 의 초기값으로 지정한다.다이나믹 프로그래밍 형식으로 2부터 k번까지 for loop 을 시행하면서 A와 B의 규칙에 따라 그 개수를 각각의 array index에 저장한다.

            aCount[i] = bCount[i - 1];  // A의 개수는 변경전 B의 개수 (B -> BA)
            bCount[i] = aCount[i - 1] + bCount[i - 1];  // B의 개수는 변경전 A와 B의 개수 (A -> B, B -> BA)

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int k = sc.nextInt();
        
        // 다이나믹 프로그래밍을 통해 A와 B의 개수를 저장할 array
        int[] aCount = new int[k + 1];
        int[] bCount = new int[k + 1];
        
        // 다이나믹 프로그래밍을 시행할 메서드
        countTheNumberOfAB(k, aCount, bCount);
        
        // 저장된 array 값을 출력
        System.out.println(aCount[k] + " " + bCount[k]);
    }
    
    public static void countTheNumberOfAB(int k, int[] aCount, int[] bCount) {
        aCount[1] = 0;  // 버튼을 한번 눌렀을때 A의 초기값
        bCount[1] = 1;  // 버튼을 한번 눌렀을때 B의 초기값

        // k번째 버튼까지 for loop 시행
        for (int i = 2; i <= k; i++) {
            aCount[i] = bCount[i - 1];  // A의 개수는 변경전 B의 개수 (B -> BA)
            bCount[i] = aCount[i - 1] + bCount[i - 1];  // B의 개수는 변경전 A와 B의 개수 (A -> B, B -> BA)
        }
    }
    
}