문제
접근
DP를 이용하여 n까지 연산하면 된다. 1234567 로 나눈 수를 반환하기 때문에 오버플로우는 걱정하지 않아도 될 것 같다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
def solution(n):
dp = [0]*(n+2)
dp[0] = 0
dp[1] = 1
if n == 1:
return 1
for i in range(2, n+1):
dp[i] = (dp[i-1] + dp[i-2]) % 1234567
return dp[n]
- C++ 코드
1
2
3
4
5
6
7
8
9
10
11
12
#include <vector>
using namespace std;
int dp[100002];
int solution(int n) {
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i<=n;i++){
dp[i] = (dp[i-1] + dp[i-2])%1234567;
}
return dp[n];
}