백준 11969번 Breed Counting

문제

Farmer John's N cows, conveniently numbered 1…N, are all standing in a row (they seem to do so often that it now takes very little prompting from Farmer John to line them up). Each cow has a breed ID: 1 for Holsteins, 2 for Guernseys, and 3 for Jerseys. Farmer John would like your help counting the number of cows of each breed that lie within certain intervals of the ordering.

문제풀이

사용한 알고리즘 : Prefix Sum

(1) 코드 5~8

 'pSum[x][k] : 0이상 x이하의 k 품종 소의 수' 라고 설정하고 배열을 만들어줍니다.

(2) 코드 13~18

 N 마리 소의 입력을 받으면서 과정(1)의 배열을 채워줍니다.

(3) 코드 19~25

 과정(2)에서 만들어 놓은 배열을 토대로 답을 출력해주면 됩니다.

	#include<bits/stdc++.h>
	using namespace std;
	int N, Q;
	//pSum[x][0] : ~x 까지 1 개수
	//pSum[x][1] : ~x 까지 2 개수
	//pSum[x][2] : ~x 까지 3 개수
	int pSum[111111][3];
	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; ++i) {
	for (int k = 0; k < 3; ++k) pSum[i][k] = pSum[i - 1][k];
	int num;
	cin >> num;
	pSum[i][num - 1]++;
	}
	for (int i = 0; i < Q; ++i) {
	int l, r;
	cin >> l >> r;
	cout << pSum[r][0] - pSum[l - 1][0] << ' ';
	cout << pSum[r][1] - pSum[l - 1][1] << ' ';
	cout << pSum[r][2] - pSum[l - 1][2] << '\n';
	}
	return 0;
	}

view raw BOJ 11969.cpp hosted with ❤ by GitHub