백준 알고리즘, 2193 문제

---

풀이

표를 그려보면 쉽게 풀 수 있다.

그러나 표의 행과 열을 어떤 수로 구성해야 할지는 약간의 고민이 필요하다. (이전 문제와는 다르다.)

문제를 보면

무조건 1 부터 시작해야하며

1 이 나오면 반드시 다음에는 0이 와야하고

0 이 나오면 다음에는 0, 1 이 모두 올 수 있다는 것을 알 수 있다.

규칙은 매우 간단하다.

여기서 바로 점화식으로 옮길 수 있다면 좋을테지만

그런 능력이 아직은 안되기 때문에

표를 그려보았다.

각각의 열은 마지막 자리가 0, 1 인 이친수의 개수를 나타낸다.

예를 들어서 살펴보면 4 자리 수의 경우

1 0 0 0

1 0 0 1

1 0 1 0

이렇게 3 개의 이친수가 존재하므로

끝자리(2^0 의 자리) 가 0 인 것은 2 개, 1 인 것은 1 개가 존재한다.

이렇게 표현해놓고 보면

0 으로 끝날 경우 다음에 2 개가 추가되고,

1 로 끝날 경우 다음에 1 개가 추가되는 특징때문에

위의 화살표와 같이 더해주면 다음 값을 알 수 있다.

점화식은 다음과 같다.

DP[N][0] = DP[N - 1][0] + DP[N - 1][1]

DP[N][1] = DP[N - 1][0]

---

코드

@github 에서 보기

/**
 * @site: https://www.acmicpc.net/problem/2193
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 07. 24
 */
#include <iostream>
using namespace std;
int main() {
    unsigned long long DP[91][2] = {0,};
    unsigned long long ans = 0;
    int i, N;
    cin >> N;
    DP[1][0] = 0;
    DP[1][1] = 1;
    for (i = 2; i <= N; i++) {
        DP[i][0] = DP[i - 1][0] + DP[i - 1][1];
        DP[i][1] = DP[i - 1][0];
    }
    ans = DP[N][0] + DP[N][1];
    cout << ans << endl;
    return 0;
}

* unsigned long long 자료형은 최대 표현값이 0 ~ 18,446,744,073,709,551,615 이기 때문에 N 이 90 자리 일때도 정확히 표현한다.