Taene's
[DP] 백준-BABBA C++ 9625번 본문
https://www.acmicpc.net/problem/9625
9625번: BABBA
상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했
www.acmicpc.net
#include <iostream>
using namespace std;
int main()
{
int dpA[46] = { 0,0,1,1, };
int dpB[46] = { 0,1,1,2, };
for (int i = 4; i <= 45; i++)
{
dpA[i] = dpA[i - 2] + dpA[i - 1];
dpB[i] = dpB[i - 2] + dpB[i - 1];
}
int k;
cin >> k;
cout << dpA[k] << ' ' << dpB[k];
return 0;
}규칙: index = i 의 A와 B의 개수가 (i-2)의 개수+(i-1)의 개수이다.
'알고리즘 문제풀이 > DP' 카테고리의 다른 글
| [DP] 백준-거스름돈 C++ 14916번 (0) | 2023.09.20 |
|---|---|
| [DP] 백준-돌 게임 C++ 9655 (0) | 2023.09.20 |
| [DP] 백준-다리놓기 C++ 1010번 (0) | 2023.09.18 |
| [DP] 백준-핸드폰번호 궁합 C++ 17202번 (0) | 2023.09.18 |
| [DP] 백준-피보나치 수 2 C++ 2748번 (0) | 2023.09.15 |
'알고리즘 문제풀이/DP' Related Articles
more
