[백준] 2193번 이친수

March 14, 2021 ( last updated : March 14, 2021 )
dp 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 2193번 이친수

[백준] 2193번 이친수

백준 2193번

dp문제 중 하나입니다. 해당 문제를 풀 때 하나 씩 직접 그려보고 숫자를 세보았습니다. 이때 다음과 같이 숫자가 나옵니다.

N 1 2 3 4 5 6 7 8
값 1 1 2 3 5 8 13 21

N이 8일 때 까지 숫자를 세고 규칙을 파악하려 노력했습니다. 그 결과 dp[n] = dp[n-1] + dp[n-2]라는 규칙을 발견했습니다. 왜 인지는 모르지만 규칙을 발견하였고 이를 통해서 문제를 풀었습니다.

문제를 푼 후 어떤 원리인지 확인해 보았는데 n-1, n-2에 있는 숫자들이 n 번째에 있는 숫자 끝에서 n-2개가 같다는 것이었습니다. 말로만은 이해가 잘 안될 테니 참고한 블로그를 링크하겠습니다.

참고 블로그

#include <iostream>

using namespace std;

int N;
long long DP[91];

int main() {
    cin >> N;
    
    DP[1] = 1;
    DP[2] = 1;
    DP[3] = 2;
    for (int i=4; i<=N; i++) {
        DP[i] = DP[i-1] + DP[i-2];
    }
    
    cout << DP[N];
    
    return 0;
}

Originally published March 14, 2021
Latest update March 14, 2021

Related posts :

{# #}