[BOJ]193この親水(ダイナミックプログラミング)


1.質問


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

2.アイデア



DP[n] = DP[n - 1] + DP[n - 2]

3.解法


1) ❌WRONG❌

  • コード
  • #include <iostream>
    using namespace std;
    
    #define N_MAX 90
    int DP[N_MAX + 1] = { 0,1,1 };
    
    int main() {
    	int N;
    	cin >> N;
    
    	for (int i = 3; i <= N; ++i) DP[i] = DP[i - 1] + DP[i - 2];
    
    	cout << DP[N] << '\n';
    	return 0;
    }
  • エラーの原因
    intの範囲外の答えも存在する.
    したがって,DPアレイのデータ型をintとすることは不適切である.
  • 2) ⭕RIGHT⭕

  • コード
  • #include <iostream>
    using namespace std;
    
    #define N_MAX 90
    long long DP[N_MAX + 1] = { 0,1,1 };
    
    int main() {
    	int N;
    	cin >> N;
    
    	for (int i = 3; i <= N; ++i) DP[i] = DP[i - 1] + DP[i - 2];
    
    	cout << DP[N] << '\n';
    	return 0;
    }