[BAEKJOON] 17203, 11441, 11969

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

 

[sliver 4, 17203 ∑|ΔEasyMAX|] - 누적 합(Prefix Sum)

1차원 누적 합 문제, 문제에서 요구하는 누적 합의 표본이 무엇인지 파악해야 한다.

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

using namespace std;

int N, Q, st, ed;
int num[1001];
int sub[1001];
int prefixSum[1001];
int main() {
	scanf("%d %d", &N, &Q);
	for (int i = 1; i <= N; i++) scanf("%d", &num[i]);
	for (int i = 1; i <= N; i++) {
		sub[i] = abs(num[i] - num[i - 1]);
		prefixSum[i] = sub[i] + prefixSum[i - 1];
	}
	for (int i = 0; i < Q; i++) {
		scanf("%d %d", &st, &ed);
		st == ed ? printf("0\n") : printf("%d\n", prefixSum[ed] - prefixSum[st]);
	}
}

 

[sliver 3, 11441 합 구하기] - 누적 합(Prefix Sum)

1차원 누적 합 문제

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

using namespace std;

int N, M, st, ed;
int num[100001];
int prefixSum[100001];
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", &num[i]);
	for (int i = 1; i <= N; i++) prefixSum[i] = num[i] + prefixSum[i - 1];
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &st, &ed);
		printf("%d\n", prefixSum[ed] - prefixSum[st - 1]);
	}
}

 

[sliver 3, 11969 Breed Counting] - 누적 합(Prefix Sum)

1차원 누적 합 문제, 하지만 누적 합을 계산할 때 다뤄야 할 데이터는 단일 ID에 대한 카운팅이므로 구조체를 활용해 풀어가는 것을 추천한다.

convenient : 편리한(형) [conveniently]
lie : 거짓말, <사람/동물>(down, back), <송장>(at, in), 위치
within : ~이내에, ~을 넘지않고, ~의 범위 내에서
certain : 확신하는, 일정한
intervals : 간격

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

using namespace std;

int N, Q, id, st, ed;

typedef struct data {
	int fs, se, th;
}Data;

int num[100001];
Data prefixSum[100001];

int main() {
	scanf("%d %d", &N, &Q);
	for (int i = 1; i <= N; i++) scanf("%d", &num[i]);
	for (int i = 1; i <= N; i++) {
		prefixSum[i] = prefixSum[i - 1];
		switch (num[i]) {
		case 1:
			prefixSum[i].fs = prefixSum[i - 1].fs + 1;
			break;
		case 2:
			prefixSum[i].se = prefixSum[i - 1].se + 1;
			break;
		case 3:
			prefixSum[i].th = prefixSum[i - 1].th + 1;
		}
	}
	for (int i = 0; i < Q; i++) {
		scanf("%d %d", &st, &ed);
		printf("%d %d %d\n", prefixSum[ed].fs - prefixSum[st - 1].fs, 
			prefixSum[ed].se - prefixSum[st - 1].se, 
			prefixSum[ed].th - prefixSum[st - 1].th);
	}
}