취미로 코딩하기

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

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

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

각 라운드를 거친 뒤의 점수 X'와 그 이전라운드까지의 그 라운드가 끝났을 때 "점수가 K보다 낮았던 라운드의 수"를 알고 있다면 이 라운드까지의 라운드가 끝났을 때 "점수가 K보다 낮았던 라운드의 수"를 계산해낼 수 있을 것이다.

위의 식을 이용해 각 라운드 k까지의 라운드가 끝났을 때 "점수가 K보다 낮았던 라운드의 수"의 값을을 미리 계산해두고 이를 이용해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, M, K, X;
int psum[100001];

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

	cin >> N >> M >> K >> X;
	for (int i = 1; i <= N; i++) {
		int A; cin >> A;
		X += A;
		if (X < K) psum[i] = psum[i - 1] + 1;
		else psum[i] = psum[i - 1];
	}
	while (M--) {
		int l, r; cin >> l >> r;
		cout << psum[r - 1] - psum[l - 1] << '\n';
	}
}