기록공간

동적 계획법을 이용하는 문제였다. 규칙을 먼저 살펴 보도록 하겠다. 1자리 -> 1 => 1개 2자리 -> 10 => 1개 3자리 -> 100, 101 => 2개 4자리 -> 1000, 1001, 1010 => 3개 5자리 -> 10000, 10001, 10100, 10101, 10010 => 5개 .... 피보나치 수열과 같은 규칙을 보이고 있다. F[i] = F[i - 2] + F[i - 1] 하지만 90자리 까지 구한다는 점에 주의를 하자. 90자리까지 표현하려면 int 범위로는 부족하기 때문이다. 코드는 다음과 같다. #include using namespace std; int main() { unsigned long long dp[90 + 1]; int input; cin >> input; dp..