반응형
알고리즘 분류 : 다이나믹 프로그래밍
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
반응형