문제
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll dp[1000004];
int main(){
cin >> n;
dp[1] = 1, dp[2]= 2;
for(int i = 3; i <= n; i++){
dp[i] = (dp[i-1] + dp[i-2]) % 15746;
}
ll ret = dp[n];
cout << ret << '\n';
}풀이
지금까지 경험으론 경우의 수를 구하라!는 다 해보거나 대부분 DP를 이용하는게 좋아보인다. 다 해보려 했으나 N이 1백만이었고 말이 안될 것이라는 생각이 들었다.
DP를 활용하려고 점화식을 생각했다.
처음 틀린 풀이는 DP[1][0] + DP[1][1] 한 자리 수 중 끝이 0인 것과 1인 것이다.
이런 식으로 2,3,4,5를 구해나갈 수 있다고 생각해서 코드를 짰으나 틀렸다. 규칙의 예외를 간과했다.
그래서 다음 생각한 것은 일단 규칙 찾으려고 다해보니까 1, 2, 3, 5 .. 즉 피보나치랑 같은 규칙을 갖고 있었다.
그래서 그대로 제출하고 마지막에 %를 해줬는데 틀렸다...
long long으로도 담을 수 없을만큼 값이 커져서 시간 초과도 아닌 틀렸습니다.가 뜨는 듯 했다. 그래서 과정 중에 나머지를 담으며 dp를 만들었고 맞았다.
결과
후기
DP라는 유형이 아무리봐도 좀 어려운듯한 느낌이 든다..
:)