https://www.acmicpc.net/problem/2560
DP와 누적 합 문제다.
#include <iostream>
using namespace std;
long long dp[1000001];
int main() {
// 입출력 속도를 단축시키기 위함
ios::sync_with_stdio(0);
cin.tie(0);
int a, b, d, N; cin >> a >> b >> d >> N;
for (int i = 0; i < a; i++) dp[i] = 1;
for (int i = a; i <= N; i++) {
if (i < b) dp[i] = (dp[i - 1] + dp[i - a] ) % 1000;
else dp[i] = (dp[i - 1] + dp[i - a] - dp[i -b] + 1000) % 1000;
}
if (N >= d) cout << (dp[N] - dp[N - d] + 1000) % 1000;
else cout << dp[N];
}
'Algorithm > DP' 카테고리의 다른 글
[C++] BOJ(백준) 20925 메이플스토리 (0) | 2023.02.22 |
---|---|
[C++] BOJ(백준) 17498 폴짝 게임 (0) | 2023.02.21 |
[C++] BOJ(백준) 2666 벽장문의 이동 (0) | 2023.02.21 |
[C++] BOJ(백준) 2225 합분해 (0) | 2023.02.12 |
[C++] BOJ(백준) 2294 동전 2 (0) | 2023.02.07 |