이친수
-
[백준] 2193번 이친수알고리즘/백준 2021. 8. 23. 17:12
문제 링크 풀이 다섯 번째 항까지 직접 경우의 수를 세어 보면 피보나치 수열과 동일한 규칙을 찾을 수 있습니다. 90번째 항까지 구해야 하는데, int형은 표현 범위를 초과하기 때문에 점화식은 long long으로 만들어줍니다. 규칙을 이렇게도 생각해볼 수 있습니다. 다섯 자리라고 할 때 10xxx0인 경우와 10xx01인 경우입니다. 0으로 끝날 때 d[n-1]과 01으로 끝나는 경우인 d[n-2]를 더해서 d[n]을 구하는 것입니다. d[n] = d[n-1] + d[n-2]이고 초기값만 잘 세팅해주면 됩니다. 코드 #include int main() { int N; scanf("%d", &N); long long d[90] = {}; d[0] = 1; d[1] = 1; for (int i = 2; i..