취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17020번 문제인 Train Tracking 2이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/17020 

구간의 최댓값과 최솟값이 주어졌을 때 배열을 어떻게 채워야하는지 관리하는지에 대한 기본 아이디어는 글쓴이의 경우 2787번 문제에서 먼저 익힌 바 있다. 풀어본 적이 없다면 저 문제를 먼저 생각해보자.

이 문제에서 추가로 필요한 관찰은 다음과 같다.

arr[x..y]의 min값을 L, arr[(x+1)..(y+1)]의 min값 R이라 하자.

1) 만약 L<R이라면 arr[x] = L이고, L>R이면 arr[y+1] = R이 된다.

2) 만약 L>=R이라면 arr[x] >= arr[x+1]이고, L<=R이라면 arr[y] <= arr[y+1]이 된다. 

위의 두 관찰을 이용하면 대략적으로 1)에서 값이 확정되는 칸에는 해당 값을, 그렇지 못한 칸들에는 해당 칸의 범위에 맞는 값을 집어넣어 문제를 해결하면 된다는 것을 알 수 있다. 단, 각 arr[x..y]와 그 min값 X에 대하여, arr[x..y]의 적어도 한 원소는 X여야 한다는 점을 놓치면 안 된다.

1)에서 값이 확정되지 않은 칸이 K개 미만 연속한다면 이 확정되지 않은 칸들을 포함하는 구간min값들은 이미 배열에 채워진 값들로 만족되고 있음을 알 수 있다. 이 경우 각 칸에 채울 수 있는 각 수의 가짓수를 답에 곱해나가자. 가짓수는 sliding window와 pq를 같이 사용하거나 그냥 구간 최댓값을 리턴하는 세그먼트 트리를 이용해 빠르게 구해낼 수 있다.

1)에서 값이 확정되지 않은 칸이 K개 이상 연속한다면, 2)에 의해 해당 칸들에 채울 수 있는 min값들이 전부 동일하게 된다. 이를 이용하면 해당 연속한 칸들에 숫자를 채워넣는 경우의 수는 DP를 이용하여 O(연속하는 칸수)에 구해낼 수 있다.

위의 과정을 적절히 구현해 문제를 해결하자.

아래는 제출한 소스코드이다.

#define MOD 1000000007
#include <iostream>
using namespace std;
typedef long long ll;

ll arr[100002];
ll rangemin[100002]; // [i]: arr[i..i+K-1]의 min
ll dpA[100002];
ll dpE[100002];

int seg[262145];
int init(int L, int R, int sI) {
	if (L == R) return seg[sI] = rangemin[L];
	return seg[sI] = max(init(L, (L + R) / 2, sI * 2), init((L + R) / 2 + 1, R, sI * 2 + 1));
}

int query(int L, int R, int qL, int qR, int sI) {
	if (qR < L || R < qL) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return max(query(L, (L + R) / 2, qL, qR, sI * 2), query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K; cin >> N >> K;
	for (int i = 1; i <= N - K + 1; i++) cin >> rangemin[i];
	init(1, 100000, 1);

	for (int i = 1; i <= N - K; i++) {
		if (rangemin[i] < rangemin[i + 1]) arr[i] = rangemin[i];
		else if (rangemin[i + 1] < rangemin[i]) arr[i + K] = rangemin[i + 1];
	}

	arr[N + 1] = 1000000007;
	int idx = 1;
	ll ans = 1;
	while (idx <= N) {
		if (arr[idx]) {
			idx++;
			continue;
		}
		
		int ii = idx;
		while (arr[ii] == 0) ii++;
		
		int diff = ii - idx;
		if (diff < K) {
			for (int q = idx; q < ii; q++) {
				ans = (ans * (ll)(1000000000 - query(1, 100000, max(q - (K - 1), 1), q, 1) + 1)) % MOD;
			}
			idx = ii;
		}
		else {
			ll CNT = 1000000000 - rangemin[idx] + 1;
			ll CNTCNT = 1;
			for (int k = 0; k < K; k++) CNTCNT = (CNTCNT * (CNT - 1)) % MOD;

			dpA[idx - 1] = 0, dpE[idx-1] = 1;
			for (int k = 0; k < K - 1; k++) {
				dpA[idx + k] = ((dpA[idx + k - 1] + dpE[idx + k - 1]) * (CNT - 1)) % MOD;
				dpE[idx + k] = (dpA[idx + k - 1] + dpE[idx + k - 1]) % MOD;
			}
			for (int k = K - 1; k < diff; k++) {
				dpA[idx + k] = ((dpA[idx + k - 1] + dpE[idx + k - 1]) * (CNT - 1) - dpE[idx + k - K] * CNTCNT) % MOD;
				if (dpA[idx + k] < 0) dpA[idx + k] += MOD;
				dpE[idx + k] = (dpA[idx + k - 1] + dpE[idx + k - 1]) % MOD;
			}

			ans = (ans * (dpA[ii - 1] + dpE[ii - 1])) % MOD;
			idx = ii;
		}
	}

	cout << ans;
}