[백준] 9625 BABBA

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

9625번: BABBA

 

난 정말 DP 가 약하다...

코테에서 나오는 DP 가 다 거기서 거기라고는 하지만 많이 안풀어봐서 방법자체를 잘 못 찾는다.

계속 풀다보면 되겠지 싶은 마음으로 브론즈부터 풀어보았다.

 

[ 풀이 ]

1. 각 스텝마다 a, b 의 갯수를 저장할 자료구조를 정의한다.

pair <int, int> DP[50];

 

2. 초기는 A 하나이므로 DP[0] = {1, 0} 이다.

 

3. 그 다음 식을 구하자

idx	a의 갯수	b의 갯수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5

a 의 갯수의 경우 이전 스텝의 b의 갯수이다.

b 의 갯수의 경우 이전 스텝의 a+b 인것을 볼 수 있다.

 

4. DP 를 쌓자

#include <iostream>
#include <vector>
using namespace std;

pair <int, int> DP[50];
int k;

int main() {
	scanf("%d", &k);

	DP[0].first = 1;
	DP[0].second = 0;

	for(int i=1; i<=45; i++) {

		int x = DP[i-1].first; // 이전에 a의 갯수
		int y = DP[i-1].second; // 이전에 b의 갯수

		int new_x = y;
		int new_y = x + y; 
		DP[i].first  = new_x;
		DP[i].second = new_y;
	}

	printf("%d %d\n", DP[k].first, DP[k].second);
}