[C++] 백준 9625번 BABBA

1. 문제이해

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

9625번: BABBA

 

상근이는 길을 걷다가, 신기한 기계를 발견했다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었고,

버튼을 누르면, 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수를 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

A와 B의 갯수를 찬찬히 살펴보면 바로 규칙을 찾을 수 있는 간단한 DP문제이다.

아래 표를 살펴보자.

 

버튼을 누른 횟수 (K)	문자열	A의 갯수	B의 갯수
1	B	0	1
2	BA	1	1
3	BAB	1	2
4	BABBA	2	3
5	BABBABAB	3	5
6	BABBABABBABBA	5	8
...	...	...	...
N	...	(N-1)번째 A의 개수 + (N-2)번째 A의 개수	(N-1)번째 B의 개수 + (N-2)번째 B의 개수

 

 

버튼을 누른 횟수 K를 점차 늘려나가며, 생성된 문자열에서 A와 B의 갯수를 세어본 표이다.

표를 보면, A와 B의 갯수는 모두 N번 버튼을 눌렀을 경우,

(N-1)번째 개수 + (N-2)번째 개수 와 동일하다는 것을 알 수 있다.

해당 식을 이용해 도출해낸 코드는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

int main() {
	int K;				// 버튼을 누른 횟수
	long long A[45];	// A의 갯수
	long long B[45];	// B의 갯수

	A[0] = 0;
	B[0] = 1;
	A[1] = 1;
	B[1] = 1;

	cin >> K;
	for (int i = 2; i < K; i++) {
		A[i] = A[i - 1] + A[i - 2];
		B[i] = B[i - 1] + B[i - 2];
	}

	cout << A[K - 1] << " " << B[K - 1];

	return 0;
}

버튼을 누른 횟수와, 횟수에 따라 생성된 문자열에서의 A와 B의 갯수를 나타내는 수열을 정의했다.

이후, A[0], A[1], B[0], B[1] 값을 초기화 해주고, i=2부터 2. 문제풀이에서 도출한 식을 이용해

K번 버튼을 눌렀을 경우의 A와 B의 갯수를 각각 구해주었다.

(수열이기때문에 0부터 시작. K번 눌렀을 때의 출력은 K-1번째 값이 된다.)

 

 

---

약 한달만의 포스팅..

결론부터 이야기하자면.. 무지 바빴고,, 앞으로는 더 바쁠 예정입니다..😱

작년에는 휴학생 신분이라 어느정도 여유가 있었는데,

올해는 졸업도 해야하고.. 프로젝트 준비에 여러모로 바쁘다보니

블로그 포스팅은 여름때까지는 뜸해질 수도 있겠네요..😭

그래도 드문드문 들어와서 포스팅 올리도록 노력해보겠습니당💪