BOJ 2193 · 이친수

알고리즘 분류 : 다이나믹 프로그래밍  

N자리 이친수를 DP를 통해 만들어야 한다.

• D[N] : N자리 이친수의 개수
• D[1] = 1, D[2] = 1
• D[N] = 0으로 끝나는 N-1자리 이친수 + 01로 끝나는 N-2자리 이친수

---

C++ 소스코드

#include <cstdio>

int n;
long long int d[91];

void solve() {
    d[1] = d[2] = 1;
    for (int i=3; i<=n; i++) {
        d[i] = d[i-1] + d[i-2];
    }
    printf("%lld\n", d[n]);
}

int main() {
    scanf("%d", &n);
    solve();
    return 0;
}

---

Python 3 소스코드

n = int(input())
d = [1]*(n+1)

def solve():
    for i in range(3, n+1):
        d[i] = d[i-1] + d[i-2]

solve()
print(d[n])

---

참고

• 백준 온라인 저지 : BOJ 2193