[백준 2193] 이친수

0. 제목

• 백준 2193 이친수
• BOJ 2193 이친수
• C++ 2193 이친수

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• dp[i][0]은 i 단계에서 0일때, dp[i][1]은 i 단계에서 1일때의 이친수 개수를 뜻한다.
• 이친수의 규칙에 의하면 1은 연속으로 나올수 없고, 0은 처음에 나올수 없다.
• 1단계에서의 dp[1][0], dp[1][1]은 각각 0, 1 로 초기화한다.
• i 단계에서 0일때, i-1 단계에서는 0, 1 둘다 올 수 있다. 따라서, dp[i-1][0] + dp[i-1][1]의 값과 같다.
• i 단계에서 1일때, i-1 단계에서는 0만 올 수 있다. 따라서, dp[i-1][0]의 값과 같다.
• N단계에서 이친수의 개수는 dp[N][0] + dp[N][1] 과 같이 구할 수 있다.
• 주의할 점으로는, 단계가 커질수록 이친수의 개수 값이 int 의 범위보다 커진다. 따라서 int보다 범위가 큰 자료형으로 설정해주었다.
• 문제에서 주어진 범위의 마지막 값을 항상 대입해 보면 좋다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int N;
    unsigned long long int dp[91][2] = {0};
    unsigned long long int sum = 0;
    
    cin >> N;
    dp[1][0] = 0;
    dp[1][1] = 1;
    
    for(int i = 2; i <= N; i++){
        dp[i][0] = dp[i-1][0] + dp[i-1][1];
        dp[i][1] = dp[i-1][0];
    }
    
    sum = dp[N][0] + dp[N][1];
    cout << sum << '\n';
    return 0;
}