본문 바로가기

Programming/BOJ

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])




참고



태그