문제
버튼을 누르면 A는 B로, B는 BA로 바뀐다. 초기 문자열 A에서 버튼을 K번 눌렀을 때, 문자열에 포함된 A와 B의 개수를 각각 구하라.
입력
첫째 줄에 K가 주어진다 (1 이상 45 이하).
출력
K번 눌렀을 때 A의 개수와 B의 개수를 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 | 1 2 |
풀이
A와 B의 개수가 각각 피보나치 수열을 따르므로 DP로 계산한다.
dp[0][i]를 i번 누른 후 A의 개수,dp[1][i]를 B의 개수로 정의한다- 초기값: 1번 후 A=0, B=1 / 2번 후 A=1, B=1 (B→BA이므로)
- i번째 상태는 이전 B들이 BA가 되고, 이전 A들이 B가 되므로
dp[i] = dp[i-1] + dp[i-2](피보나치 점화식) dp[0][K]와dp[1][K]를 출력한다
핵심 아이디어: A→B, B→BA 변환에서 A와 B의 개수 변화는 각각 피보나치 수열을 따른다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day308BOJ9625BABBA {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int k = Integer.parseInt(br.readLine());
int[][] dp = new int[2][46];
dp[0][2] = 1;
dp[1][1] = 1;
dp[1][2] = 1;
for (int i = 3; i <= k; i++) {
dp[0][i] = dp[0][i - 2] + dp[0][i - 1];
dp[1][i] = dp[1][i - 2] + dp[1][i - 1];
}
System.out.print(dp[0][k] + " " + dp[1][k]);
br.close();
}
}복잡도
- 시간: O(K)
- 공간: O(K)