백준 26007번 : Codepowers - C++

 

제가 다니고 있는 대학 프로그래밍 경진대회에 출제되었던 문제입니다.
대회 중에는 시간초과로 결국 해결하지 못했었던 것 같은데, 이번에 다시 풀어보았습니다.

첫째 줄에 N, M, K, X 정수가 주어지고,

둘째 줄에는 N개의 정수가 주어지는데, 차례대로 직전 라운드 대비 점수가 얼마나 증감되었는지에 대한 값입니다.

세번째 줄부터는 M줄에 거쳐 몇 라운드부터 몇 라운드 직전까지 K보다 낮은 점수를 받았던 횟수가 얼마인지에 대한 정보가 주어집니다.

 

중복 계산을 최대한 줄이기 위해 둘째 줄에 주어진 정보를 가공하기로 했습니다.

문제 해결에 있어서 점수 그 자체는 그다지 중요하지 않고, 다만 K보다 점수가 높은지, 낮은지에 대한 정보만 필요하다는 점을 고려합니다.

 

두 라운드 간의 점수를 비교하기만 하면 되기 때문에, 주어진 정보로 실제 점수를 만든다거나하는 불필요한 연산은 하지 않기로 했습니다.

 

둘째 줄에 주어진 정보는 직전 라운드 대비 점수가 얼마나 늘어나고 줄었는지에 대한 정보이므로, 이를 처음부터 차례대로 합산하면 (해당 라운드 점수 - X)이 됩니다. 이를 (K - X)값과 비교하는 것으로 라운드 점수가 K보다 높은지 낮은지 비교하는 것이 됩니다.

 

위 정보(예시 속 accu)를 바탕으로 인덱스 값에 해당하는 라운드의 점수가 K보다 낮은지 저장하는 배열 하나 - (예시 속 isLower),

인덱스 값에 해당하는 라운드까지, K보다 낮은 점수를 받았던 횟수의 총합을 저장하는 배열 하나 - (예시 속 lowerSum)

를 만들었습니다.

 

문제 예시 값을 가공했을 때 결과.

 

두 배열을 사용하면 각 라운드의 점수를 여러 번 검색하여 비교할 필요 없이, 두 라운드 번호 값 사이 (isLower == 1)인 경우가 몇 번 있었는지 빠르게 찾을 수 있습니다.

 

첫번째 테스트케이스로 3과 6이 주어졌으므로, 라운드 5과 3에 해당하는 lowerSum값을 서로 뺍니다. (몇 라운드부터 몇 라운드 직전까지이므로)

여기에 라운드 3의 isLower가 1 이므로 앞에서 뺀 값에 1을 더해 출력합니다. 

 

마지막 테스트케이스로 9와 11이 주어졌으므로, 라운드 10과 9에 해당하는 lowerSum값을 서로 뺍니다.

라운드 9의 isLower가 0 이므로 그대로 출력합니다.

 

#include <iostream>

using namespace std;

int isLower[100001];
int lowerSum[100001];

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

	int n, m, k, x;
	cin >> n >> m >> k >> x;

	int temp;
	int diff = k - x;
	int accu = 0;

	for (int i = 1; i <= n; ++i) {
		cin >> temp;
		accu += temp;
		lowerSum[i] = lowerSum[i - 1];

		if (accu < diff) {
			isLower[i] = 1;
			lowerSum[i]++;
		}
	}

	int s, e;
	for (int i = 0; i < m; ++i) {
		cin >> s >> e;

		if (isLower[s] == 1) cout << lowerSum[e - 1] - lowerSum[s] + 1 << "\n";
		else cout << lowerSum[e - 1] - lowerSum[s] << "\n";
	}

	return 0;
}