[C++] BOJ 9625 RIJEČI (BABBA)

문제

백준 9625번 BABBA

www.acmicpc.net/problem/9625

9625번: BABBA

코드

#include<iostream>
using namespace std;

int arr[50][2];
//arr[i][0]:number of A, arr[i][1]: number of B
int k;
int main() {
	arr[0][0] = 1;
	arr[0][1] = 0;
	cin >> k;
	for (int i = 1; i <= k; i++) {
		arr[i][0] = arr[i-1][1];
		arr[i][1] = arr[i - 1][0] + arr[i - 1][1];
	}
	cout << arr[k][0] << " " << arr[k][1];
}

풀이방법

입력값이 k일때 A, B의 개수는 입력값이 (k-1)일 때의 A, B의 개수와 규칙성이 있으므로 동적계획법을 이용한다. arr[i][0]은 A의 개수, arr[i][1]은 B의 개수를 나타낸다.