백준 2560번, 짚신벌레 풀이

문제

백준 2560번

풀이

문제의 지문에서는 짚신 벌레가 산 날을 기준으로 예시를 보여주었는데, 짚신 벌레가 태어난 날을 기준으로 예제 테스트 케이스를 풀어보겠습니다.

짚신벌레 table

각 표의 번호는 짚신 벌레가 태어난 날입니다.

2번째 날에는 0번째 날(처음 들어있는 짚신벌레)로부터 태어나므로 0 -> 2라고 적었고, 아래 표도 비슷한 방법으로 적었습니다.

 

위 표에서 $day$일에 태어난 짚신벌레의 수를 $cnt[day]$라고 정의합니다.

 

$day$일 때 얼마의 짚신벌레가 태어나는지, 얼마의 짚신벌레가 죽는지 알아봅시다.

 

 

$k$일에 태어난 짚신벌레는 $day-k$일만큼 살았다고 표현할 수 있고, 문제에서 주어진 조건에 따라 아래와 같은 부등식을 세울 수 있습니다.

 

$$a \leq day - k \leq b - 1$$

 

$k$에 대해 정리하기 위해 각 항에 $ -day $를 더해주고, $-1$을 곱해주면 아래와 같은 부등식이 나옵니다.

 

$$day - b + 1 \leq k \leq day - a$$

 

즉, $day$일에는 자식을 생산할 수 있는 짚신벌레의 범위가 위와 같습니다.

그런데, $day$가 $1$씩 증가하므로, $day - 1$일일 때 생산 가능 짚신벌레의 수가 $sum$이였다면, $day$일에는 생산 가능 짚신벌레의 수는 $sum - cnt[day - b] + cnt[day - a]$가 됩니다. (단, $b \leq day, a \leq day$)

 

죽는 짚신 벌레 역시 비슷하게 구할 수 있습니다.

$k$일에 태어난 짚신벌레는 $day-k$일만큼 살았다고 표현할 수 있고, 문제에서 주어진 조건에 따라 아래와 같은 부등식을 세울 수 있습니다.

 

$$day - k \leq d - 1$$

$$k \geq day - d $$

 

위 부등식은 살아있는 짚신벌레의 수의 범위로,

$day - 1$일에 살아있는 짚신벌레의 수가 $ans$였다면, $day$일에는 $cnt[day - d]$만큼의 짚신벌레가 더 죽어 $ans + cnt[day - d]$가 됨을 의미합니다.

 

 

이 문제의 핵심은 죽는 짚신벌레와 생산 가능한 짚신벌레의 범위가 연속임을 이용하여 $day$를 증가시킬 때 빼야할 것과 더할 것을 나누는 것입니다.

 

* PS) 1000으로 나눈 나머지에 뺄셈을 할 때 1000을 미리 더해 나눠야 제대로 답이 나옵니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef unordered_map<int, int> mpii;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int a, b, d, n, ans = 1, sum = 0; cin >> a >> b >> d >> n;
	vi cnt(n + 1);
	cnt[0] = 1;
	for (int i = 1; i <= n; i++) {
		if (i >= b) sum -= cnt[i - b] - 1000, sum %= 1000;
		if (i >= a) sum += cnt[i - a], sum %= 1000;
		cnt[i] = sum;
		ans += cnt[i];
		if (i >= d) ans -= cnt[i - d] - 1000, sum %= 1000;
	}
	cout << ans % 1000;
}