[BOJ 13982 // C++] Shopping

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

 

이번에 볼 문제는 백준 13982번 문제인 Shopping이다.
문제는 아래 링크를 확인하자.

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

13982번: Shopping

개당 Ai원인 i번째 물건을 산 직후라면 현재 소지금은 Ai 미만이 된다. 따라서 최악의 경우(돈이 가장 많이 남은 경우) 다음으로 살펴봐야하는 가게는 i보다 나중에 있으면서 Ai보다 싼 물건이 된다. 각 물건마다 최악의 경우 다음에 사게 되는 물건을 방향그래프로 이은 그래프(없다면 0번 물건으로 잇자)를 하나 만들면 이 그래프는 모든 노드의 outdegree가 1이라는 특징이 생긴다.

 

위 그래프 위에서 에지를 따라 이동한 횟수가 2^k이면 어디로 이동하게 되는지를 저장해 둔 sparse table을 작성해두면 O(lgN)에 항상 다음으로 물건을 사게 되는 가게를 빠르게 구해낼 수 있게 된다. 소지금이 V일 때 물건을 한 종류 산다면 V는 절반 이하로 떨어진다는 것을 관찰하면 손님 한 명당 O(lgV)회의 그래프 이동으로 항상 물건 구입을 시뮬레이션할 수 있게 됨을 알 수 있다.

 

위 풀이의 최종 시간복잡도는 O(QlgNlgV)이다.

 

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

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;

int N, Q;
stack<int> stk;
ll nxt[19][200001];
ll MOD[200001];

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

	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> MOD[i];
		while (!stk.empty()) {
			if (MOD[stk.top()] > MOD[i]) {
				nxt[0][stk.top()] = i;
				stk.pop();
			}
			else break;
		}
		stk.push(i);
	}

	for (int k = 1; k < 19; k++) {
		for (int i = 1; i <= N; i++) {
			nxt[k][i] = nxt[k - 1][nxt[k - 1][i]];
		}
	}

	while (Q--) {
		ll val, L, R; cin >> val >> L >> R;
		while (MOD[L] && L <= R) {
			val %= MOD[L];
			for (int i = 18; i > -1; i--) {
				if (MOD[nxt[i][L]] > val) L = nxt[i][L];
			}
			L = nxt[0][L];
		}

		cout << val << '\n';
	}
}