[BAEKJOON] 10986, 11997, 16507, 16713, 10211

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[sliver 4, 10211 Maximum Subarray] - 누적 합(Prefix Sum)

1차원 누적 합, 최종 결과 값이 음수 일 때를 놓치지 말자

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int N;
int num[1001];
int prefixSum[1001];
int main() {
	int tc;
	scanf("%d", &tc);
	for (int t = 0; t < tc; t++) {
		int answer = -1001;
		scanf("%d", &N);
		for (int i = 1; i <= N; i++) {
			scanf("%d", &num[i]);
			prefixSum[i] = num[i] + prefixSum[i - 1];
		}
		for (int i = 1; i <= N; i++) {
			answer = max(answer, prefixSum[i]);
			for (int j = 1; j < i; j++) {
				answer = max(answer, prefixSum[i] - prefixSum[j]);
			}
		}
		printf("%d\n", answer);
	}
}

 

[sliver 2, 16713 Generic Queries] - 누적 합(Prefix Sum)

1차원 누적 합, 하지만 기존의 뺄셈 연산이 아닌 XOR 연산이 사용되었으므로 점화식에 대한 검증이 필요하다.

 

설명을 위해 []을 배열 ()을 구간, <>을 누적합이라고 표현하겠다.

 

내가 [1, 2, 3]이란 배열을 가지고 있고, (2 ~ 3)에 대한 누적 합을 구하려면 다음과 같이 진행됐었다.

 

(2 ~ 3)은 (1 ~ 3)에서 <1>을 뺀 것과 같다.

(1 ~ 1)은 <0> + (1) = 0 + 1 = 1,

(1 ~ 2)는 <1> + (2) = 1 + 2 = 3,

(1 ~ 3)은 <2> + (3) = 3 + 3 = 6,

(2 ~ 3)은 <3> - <1> = 6 - 1 = 5, (2 ~ 3)을 직접 구하면 2 + 3 = 5으로 동치이기 때문에

구간 (st ~ ed)에 대하여 점화식 prefixSum[ed] - prefixSum[st]가 도출되게 된다.

 

이를 XOR연산으로 변경하여 대입하고, 결과가 동치인지 확인해보자

(2 ~ 3)은 (1 ~ 3)에서 <1>을 XOR한 것과 같다.

(1 ~ 1)은 <0> ^ (1) = 0 ^ 1 = 1,

(1 ~ 2)는 <1> ^ (2) = 1 ^ 2 = 01 ^ 10 = 11 = 3,

(1 ~ 3)은 <2> ^ (3) = 3 ^ 3 = 11 ^ 11 = 00 = 0,

시작부터 끝까지 XOR 연산을 진행하는 모습은, 기존의 뺄셈 연산을 진행한 것과 동일한 모습을 보였다. 그렇다면 구간에 대한 모습은 어떨까

 

(2 ~ 3)은 <3> ^ <1> = 0 ^ 1 = 1, (2 ~ 3)을 직접 구하면 2 ^ 3 = 10 ^ 11 = 01 = 1으로 동치이기 때문에

구간 (st ~ ed)에 대하여 점화식 prefixSum[ed] ^ prefixSum[st - 1]이 도출되게 된다.

이를 활용해서 문제를 풀어가도록 하자.

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int N, Q, st, ed, answer;
int num[1000001];
int prefixSum[1000001];
int main() {
	scanf("%d %d", &N, &Q);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &num[i]);
		prefixSum[i] = num[i] ^ prefixSum[i - 1];
	}

	for (int q = 0; q < Q; q++) {
		scanf("%d %d", &st, &ed);
		answer ^= prefixSum[ed] ^ prefixSum[st - 1];
	}

	printf("%d", answer);
}

 

[sliver 1, 16139 인간-컴퓨터 상호작용] - 누적 합(Prefix Sum)

1차원 누적 합 문제, 하지만 테케를 진행하는 시간이 촉박한 문제다. 나는 다음과 같은 방법에서 실패를 겪었다.

 

※ map, unordered_map stl 사용

문자열을 다루고, 카운팅하는 시점에서 map을 떠올렸다. <char, int> 형식의 prefixSum을 만들어주고 문자에 대한 누적 합을 진행하면 됐다. 하지만 stl의 경우 시간싸움에는 불리하다.

 

다음은 map<string, int>, unordered_map<string, int>, map<int, int>, int array, char array에 대해 10000회의 테스트를 진행한 결과를 (초)단위로 나타낸 지표이다.

(출처: https://spikez.tistory.com/294 [미카 프로젝트:티스토리])

함수	데이터 형식	1	2	3	4
stringMapTC()	std::map <const std::string, int>	0.0049	0.0052	0.0054	0.0053
stringUnorderedMapTC()	std::unordered_map <const std::string, int>	0.0018	0.0019	0.0019	0.0019
intMapTC()	std::map <int, const std::string>	0.0006	0.0008	0.0008	0.0008
intArrayTC()	std::array <std::string, 100>	0.0001	0.0001	0.0001	0.0001
cArrayTC()	char* srcStr[]	0.0001	0.0001	0.0001	0.0001

(출처: https://spikez.tistory.com/294 [미카 프로젝트:티스토리])

unordered_map의 경우, map보다 약 3배정도 빠른 지표를 보여주고 있으나, int/char array에 비해선 18배 느린 모습을 볼 수 있다. 그래서 이번 문제를 해결하기에 map stl은 적합하지 않고 2차원 배열로 알파벳을 카운팅 하는 것이 바람직하다.

 

※ 버퍼에 남는 '\0'

c++에서 cin/cout을 사용한다면 다음 구문을 입력하여, cin/cout의 수행시간을 줄일 수 있다.

ios_base::sync_with_stdio(false);
cin.tie(0);	// NULL
cout.tie(0);	// NULL

cin 자체도 문자열을 다룰 때, 버퍼에 남는 '\0'을 제거하기 위해선 cin.ignore()을 사용해 주어야 한다. 하지만, 이 경우는 공백을 포함한 문자열을 받기 위해 getline(cin, value, '\0')을 사용할 때만 필요하므로 이번 케이스와는 별개이다.

 

c++ scanf를 사용할 때 버퍼에 무조건 '\0', 개행문자가 남게 된다. 특히 이번 문제와 같이 하나의 문자를 반복적으로 입력받을 때 많이 거슬리는 상황이다. 이때 버퍼에 남은 개행문자를 제거하기 위해선 다양한 방법을 사용할 수 있으나, getchar()를 활용하여 버퍼를 초기화 시키지 않고 개행문자를 입력받았다.

하지만 c에서 scanf를 사용한다면

1) scanf("%*c", value) = 입력은 받되, 저장은 하지 않음,

2) scanf(" %c", value) = white space를 구분자로 인식,

위와 같은 방법을 사용하지만, 해당 방법이 이번 문제를 해결하는 데 도움이 되진 않는 내용이다. 그래서 버퍼를 완전히 비우기 위한 방법(rewind(stdio) = 매개변수로 들어온 stream을 초기화)을 사용해 보자

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int Q, st, ed, answer;
char alphabet;
char word[200001];
int prefixSum[200001][26];

int mstrlen(char* word) {
	int cnt = 0;
	for (int i = 0; word[i] != '\0'; i++) cnt++;
	return cnt;
}
int main() {
	scanf("%s", &word);

	int len = mstrlen(word);

	for (int i = 1; i <= len; i++) {
		for (int j = 0; j < 26; j++) {
			prefixSum[i][j] = prefixSum[i - 1][j];
		}
		prefixSum[i][word[i - 1] - 'a'] += 1;
	}

	scanf("%d", &Q);
	for (int q = 0; q < Q; q++) {
		getchar();
		scanf("%c %d %d", &alphabet, &st, &ed);
		printf("%d\n", prefixSum[ed + 1][alphabet - 'a'] - prefixSum[st][alphabet - 'a']);
	}
}

 

[sliver 1, 16507 어두운 건 무서워] - 누적 합(Prefix Sum)

2차원 누적 합 문제, 시작점과 끝점 사이의 배열의 갯수로 기존의 누적합을 나누어 주는 것에 유념하자.

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int R, C, Q;
int sy, sx, ey, ex;
int picture[1001][1001];
int prefixSum[1001][1001];

int main() {
	scanf("%d %d %d", &R, &C, &Q);
	for (int r = 1; r <= R; r++)
		for (int c = 1; c <= C; c++) {
			scanf("%d", &picture[r][c]);
			prefixSum[r][c] = picture[r][c]
				+ prefixSum[r - 1][c]
				+ prefixSum[r][c - 1]
				- prefixSum[r - 1][c - 1];
		}

	for (int q = 0; q < Q; q++) {
		scanf("%d %d %d %d", &sy, &sx, &ey, &ex);
		int calc = (prefixSum[ey][ex]
			+ prefixSum[sy - 1][sx - 1]
			- prefixSum[ey][sx - 1]
			- prefixSum[sy - 1][ex])
			/ ((ey - sy + 1) * (ex - sx + 1));
		printf("%d\n", calc);
	}
}

 

[gold 3, 10986 나머지 합] - 누적 합(Prefix Sum)

1차원 누적 합으로 풀이한다면 10^6*10^6이기 때문에 시간 초과를 경험할 수 있다. 그래서 이번 문제는, 누적 합의 개념을 응용하여 풀어야 한다.

 

문제에서는 Moduler 연산을 적용한 누적 합에 대해 나누어 떨어지는 구간을 찾기를 원했다. 그 구간은 다음과 같이 찾아낼 수 있다.

1) 현재까지 누적값이 0으로 나누어떨어지는 경우,

2) 특정 구간의 누적값이 0으로 나누어떨어지는 경우

1)은 쉽게 구할 수 있으나, 2)의 경우 Moduler 연산의 특징을 활용해야 한다는 생각을 키워야 한다.

 

특정 구간이란, (st ~ ed)에 해당하는 prefixSum[st], prefixSum[ed] 두 구간을 뺄셈했을 때를 의미한다. 이것에 대해 설명하기 위해 아래 예시를 잠시 들여다보자.

 

누적 합에 Moduler 연산을 적용하면 다음과 같은 모습을 보여준다.

만약 MOD value가 5이고 결과 값이 0, 1, 4, 1, 2, 3, 2로 나타날 때, 우리는 5 미만의 결과 값이 반복되는 것을 알 수 있다. 이때 동일한 결과 값을 가진 구간을 선택해서, 한 구간을 빼준다면 우리는 0으로 나누어떨어지는 구간을 얻을 수 있다.

[1, 3, 2, 4, 1, 2]라는 배열이 주어질 때, 구간 합은 [1, 4, 6, 10, 11, 13]이 되고, MOD 5의 결과는 [1, 4, 1, 0, 1, 3]이 된다. 이때 (1 ~ 1)과, (1 ~ 3)구간을 선택하여 (1 ~ 1)구간을 제거해주면 (2 ~ 3)을 얻고 (4 + 6) % 5 = 0이란 결과를 얻을 수 있다.

 

여기서 우리는 prefixSum[ed] % MOD == prefixSum[st] % MOD인 쌍이 (st ~ ed) % MOD = 0을 만족함을 알 수 있다. 이를 활용하여 문제를 풀어주자. 문제에서 M <= 10^3 이므로, MOD 값을 인덱스로 카운팅 한다면 더 쉽게 문제를 풀어나갈 수 있을 것이다.

 

이 문제는 10억 미만의 A가 입력된다. 따라서, 합산하는 자료형을 long long으로 신경써주어야 한다.

누적 합을 MOD한 결과 카운팅 값은 최대 100만이 되어 100*99/2 = 5000억의 결과값을 만들어 낼 수 있으므로, 정답 값의 자료형 또한 long long으로 신경써주어야 한다.

또한, 정답 값에 합산되는 카운팅 값의 자료형을 정답 값과 동일하게 맞춰주어야 한다. 자료형이 자동 형 변환 되면서 정답 값이 변동될 수 있기 때문이다.

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int N, M, num;
long long sum, answer;
long long prefixSum[1001];
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &num);
		sum += num;
		prefixSum[sum % M]++;
	}
	for (int i = 0; i < M; i++) {
		// 5C2 = 5x4/2x1, nC2 = n*(n-1)/2
		answer += prefixSum[i] * (prefixSum[i] - 1) / 2;
	}
	// 조합하지 않아도 MOD 0을 만족하는 기본 구간 추가
	printf("%lld\n", answer + prefixSum[0]);
}