[BOJ/Gold 3] 백준 2900 프로그램(C++)

문제 링크

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

2900번: 프로그램

 

문제

창영이가 에러를 찾기 위해서 디버깅을 하고 있다. 이 프로그램은 크기가 N이고 0으로 채워져있는 배열을 a를 만들고, 아래 something 함수를 호출한다.

void something(int jump) {
    int i = 0;
    while (i < N) {
        a[i] = a[i] + 1;
        i = i + jump;
    }
}

창영이는 함수를 K번 호출하려고 한다. 각각 호출할 때, 인자로 넘기는 jump의 값은 X1, X2, X3, ... Xk 순서이다.

이렇게 호출한 뒤에는 배열의 값이 정상적으로 들어갔는지를 확인하려고 한다. 확인은 총 Q번 하고, 매번 확인을 할 때마다 L과 R(L ≤ R)을 정한뒤, 그 구간의 배열의 합을 구한다. 즉, a[L] + a[L+1] + ... + a[R]을 구한다.

함수를 호출할 때 필요한 X의 값과 창영이가 확인한 횟수 Q가 주어졌을 때, 확인한 결과(배열의 합)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N과 함수의 호출 횟수 K가 주어진다. (1 ≤ N, K ≤ 106)

둘째 줄에 함수를 호출할 때 사용하는 인자의 값 X1, X2..., Xk가 공백으로 구분되어 주어진다. (1 ≤ Xi < N)

셋째 줄에는 확인하는 횟수 Q가 주어진다. (1 ≤ Q ≤ 106)

넷째 줄부터 Q개 줄에는 각 확인에 사용하는 L과 R이 주어진다. (0 ≤ L ≤ R < N)

출력

출력은 총 Q줄이다. 창영이가 확인하는데 사용한 L과 R이 주어졌을 때, a[L] + a[L+1] + a[L+2] ... + a[R]을 출력한다. 

예제 입력 1

10 4
1 1 2 1
3
0 9
2 6
7 7

예제 출력 1

35
18
3

예제 입력 2

11 3
3 7 10
3
0 10
2 6
7 7

예제 출력 2

8
2
1

예제 입력 3

1000000 6
12 3 21 436 2 19
2
12 16124
692 29021

예제 출력 3

16422
28874

알고리즘 분류

• 누적 합

풀이

K개의 Jump 인자를 받으면서 각 Jump가 몇 개 나왔는지 map을 통해 기록한다.

1개 이상 입력받은 Jump 인자들을 매개변수로 하는 something 함수를 수행한다.

이 때, 1을 더하는 대신에 각 Jump 인자들을 입력받은 횟수를 더하면 시간을 절약할 수 있을 것이다.

마지막으로 배열 A의 누적 합을 기록한 배열 Sum을 선언하고 누적 합을 기록한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1000001
#define LL long long
#define INF 1e9

using namespace std;
int N, K, Q, X;
unordered_map<int, int> MAP;
unordered_map<int, int>::iterator IT;
LL A[MAX];
LL Sum[MAX];

void Input() {
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		cin >> X;
		MAP[X]++;
	}
	cin >> Q;
}

void Settings() {
	for (IT = MAP.begin(); IT != MAP.end(); IT++) {
		int IDX = 0;
		while (IDX < N) {
			A[IDX] += IT->second;
			IDX += IT->first;
		};
	}
	for (int i = 1; i <= N; i++) {
		Sum[i] = A[i - 1] + Sum[i - 1];
	}
}

void Find_Answer() {
	while (Q--) {
		int L, R;
		cin >> L >> R;
		L++;
		R++;
		cout << Sum[R] - Sum[L - 1] << "\n";
	};
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}