[백준 2193] 이친수(C++)

이친수

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

문제 접근

• DP 문제집을 통해 접근한 것이 아니었다면 백트래킹인가? 했을 것이다.
  적절한 알고리즘을 선택할 수 있는 안목을 길러야겠다.
• 1로 시작해야 한다는 조건과 연속된 1이 나올 수 없다는 조건을 만족하는 방법의 개수를 세는 문제이다.

풀이 힌트

• table 정의와 점화식, 초기값을 발견하기 위해 값을 직접 대입해보았다.
• 첫째 자리가 1로 시작하면 앞에 두 자리는 1과 0으로 고정이 된다는 사실을 발견했다.
  아래 그림을 보자.

• 규칙성을 발견했는가?

• 피보나치 수열이었다.
• 앞의 2자리 수는 1 0 으로 고정되어있기 때문에 앞의 2자리를 제외한 자리의 경우의 수가 중요하다.

• 7개까지 끄적이며 찾아보다가 피보나치 수열이 확실하다고 생각하여 바로 제출하고 AC를 받았다.
• 하지만 난데없이 웬 피보나치 수열이란 말인가?

피보나치 수열이 나오는 이유

https://www.acmicpc.net/board/view/48107

질문 게시판을 뒤져 답을 얻었다.

피보나치 수열이 나오게 되는 유명한 케이스라는 것이 놀랍다.

코드

• 코드

int main() {
    int N;
    long long cnt[91];
    
    cin >> N;

    cnt[1] = 1;
    cnt[2] = 1;
    for (int i = 3; i <= N; ++i) {
        cnt[i] = cnt[i - 1] + cnt[i - 2];
    }
    cout << cnt[N];
}

• 피보나치 수열의 구현이므로 자세한 설명은 생략하겠다.
• 50까지만 가더라도 21억을 가뿐히 넘기 때문에 long long 자료형을 사용해야 한다.

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.