백준 9625 BABBA [Java]

풀이1

---

0번: A
1번: B
2번: BA
3번: BAB
4번: BABBA
.
.
.
버튼을 i번 눌렀을 때 i-1번과 i-2번을 합친 것과 같은 규칙을 발견(i>=2)

---

코드

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());  
		String s = "A";  
		String [] dp = new String[45+1];
		
		dp[0] = "A";
		dp[1] = "B";
		
		for(int i=2; i<46; i++) dp[i] = "";
		
		
		for(int i=2; i<=k; i++) {
			dp[i] += dp[i-1] + dp[i-2];
		}

		
		int len = dp[k].length();
		dp[k] = dp[k].replace("A", "");
		int a = len - dp[k].length();
		int b = dp[k].length();
		
		System.out.println(a + " " + b);	
		
	}
}

하지만 메모리 초과가 뜸

어떻게 문제를 풀까 하다가 String 배열에 각 단계의 문자열을 저장하기 보다는 A와 B의 개수를 직접 구해보기로 변경
버튼 횟수에 따른 A와 B의 개수에 규칙이 있나 살펴봄

버튼을 2번째 눌렀을 때 부터 i번째의 A(혹은 B)의 개수는 i-1과 i-2번째의 개수를 구하면 된당... 생각해보니까 위에 풀이랑 같은 원리인데 인지하지 못한 나의 능지

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());  //버튼 누르는 수
		
		int [] dpA = new int[46];
		int [] dpB = new int[46];
		
		dpA[0] = 1;		//A 1개, B 0개
		dpB[0] = 0;
		
		dpA[1] = 0;		//A 0개, A 1개
		dpB[1] = 1;
		
		for(int i=2; i<=k; i++) {
			dpA[i] = dpA[i-1] + dpA[i-2];
			dpB[i] = dpB[i-1] + dpB[i-2];
		}
		
		System.out.println(dpA[k] + " " + dpB[k]);
	}
}

2023-03-09