백준11969(Breed Counting)

jh Seo·2022년 12월 26일

구간합배열 백준 한번에 푼 문제

백준

목록 보기

110/194

개요

백준 11969번: Breed Counting

입력
The first line of input contains (N) and (Q) ((1 \leq N \leq 100,000), (1 \leq Q \leq 100,000)).

The next (N) lines contain an integer that is either 1, 2, or 3, giving the breed ID of a single cow in the ordering.

The next (Q) lines describe a query in the form of two integers (a, b) ((a \leq b)).
출력
For each of the (Q) queries ((a,b)), print a line containing three numbers: the number of cows numbered (a \ldots b) that are Holsteins (breed 1), Guernseys (breed 2), and Jerseys (breed 3).

접근 방식

단순히 번역해보면 각 입력마다 1,2,3로 나타내는 소 종류값이 순서대로 들어오고, a번쨰 순서부터 b번째 순서까지 소가 종류별로 몇마리씩 있나를 구해야하는 문제다.
이 문제도 역시나 N과 Q의 범위가 10만이 넘으므로
단순히 입력값 받아서 해당 입력값마다 몇마리인지 순서대로 구해가면
시간 복잡도가 O(N*Q)로 시간초과가 나온다.

따라서 합배열을 미리 선언해서 각 입력마다 더해서 합배열을 구현한다.

소의 종류가 세 개이므로 세가지 값을 가진 구조체를 선언한 후,

//각 입력값마다 1,2,3 몇개씩있는지 정보를 담을 구조체 
struct cowInfo{
	int Holsteins;
	int Guernseys;
	int Jerseys;
};

//구조체 연산자 오버로딩
cowInfo operator-(const cowInfo& c1, const cowInfo& c2) {
	cowInfo ret;
	ret.Holsteins = c1.Holsteins - c2.Holsteins;
	ret.Guernseys = c1.Guernseys - c2.Guernseys;
	ret.Jerseys = c1.Jerseys - c2.Jerseys;
	return ret;
}

각 입력값 마다 해당 순서에서의 소의 상황을 저장할 벡터를 선언했다.

//v[i]는 i번째일때 소 정보 
vector<cowInfo> v;

구조체를 안쓰고 구현하려면 2차원 배열을 통해 각 순서에 대해 0,1,2값이 몇개인지를
판별하면된다.

cowInfo구조체를 통해 구현한 코드

#include<iostream>
#include<vector>

using namespace std;

int N=0, Q=0;
int dx[3] = { 0,1,2 };

//각 입력값마다 1,2,3 몇개씩있는지 정보를 담을 구조체 
struct cowInfo{
	int Holsteins;
	int Guernseys;
	int Jerseys;
};

//구조체 연산자 오버로딩
cowInfo operator-(const cowInfo& c1, const cowInfo& c2) {
	cowInfo ret;
	ret.Holsteins = c1.Holsteins - c2.Holsteins;
	ret.Guernseys = c1.Guernseys - c2.Guernseys;
	ret.Jerseys = c1.Jerseys - c2.Jerseys;
	return ret;
}

//v[i]는 i번째일때 소 정보 
vector<cowInfo> v;

void Input() {
	cowInfo back={0,0,0};
	//tmp for N / tmp1,tmp2 for Q
	int tmp = 0,tmp1=0,tmp2=0;
	cin >> N >> Q;
	v.push_back(back);
	//입력값이 1,2,3인지에 따라 마지막 cowinfo에 증가시켜주고 벡터에 저장
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		back = v.back();
		if (tmp == 1) {
			back.Holsteins++;
			v.push_back(back);
		}
		else if (tmp == 2) {
			back.Guernseys++;
			v.push_back(back);
		}
		else {
			back.Jerseys++;
			v.push_back(back);
		}
	}
	//Q번간 a,b입력받아 각 a,b에 대해 답출력
	for (int i = 0; i < Q; i++) {
		cin >> tmp1 >> tmp2;
		//0~tmp2 값의 합부터 0~ (tmp1-1)값의 차가 답이된다.
		cowInfo ans=v[tmp2] - v[tmp1-1];
		cout << ans.Holsteins<< " " << ans.Guernseys << " " << ans.Jerseys << '\n';
	}
}



int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

2차원 배열을 이용한 코드

////////////////////////////////////////////// by array 

#include<iostream>
#include<vector>

using namespace std;

int N = 0, Q = 0;

//0 for Holsteins, 1 for Guernseys, 2 for Jerseys
int cowInfo[100'001][3];

void Input() {

	//tmp for N / tmp1,tmp2 for Q
	int tmp = 0, tmp1 = 0, tmp2 = 0;
	cin >> N >> Q;
	//입력값이 1,2,3인지에 따라 해당 순서의 tmp-1값을 증가시켜 저장
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		for (int j = 0; j < 3; j++) {
			//cowInfo[i+1][tmp-1]은 i번째까지의 tmp-1에 해당하는 소의 갯수 
			//j가 tmp일때 ==연산자를 이용해 1 계산
			cowInfo[i + 1][j] = cowInfo[i][j]+(j==tmp-1);
		}
	}
	//Q번간 a,b입력받아 각 a,b에 대해 답출력
	for (int i = 0; i < Q; i++) {
		cin >> tmp1 >> tmp2;
		//0~tmp2 값의 합부터 0~ (tmp1-1)값의 차가 답이된다.
		for (int j = 0; j < 3; j++) {
			cout << cowInfo[tmp2][j] - cowInfo[tmp1 - 1][j] << " ";
		}
		cout << '\n';
	}
}



int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

배열 방식을 통해 풀었을 때,

for (int j = 0; j < 3; j++) {
			//cowInfo[i+1][tmp-1]은 i번째까지의 tmp-1에 해당하는 소의 갯수 
			//j가 tmp일때 ==연산자를 이용해 1 계산
			cowInfo[i + 1][j] = cowInfo[i][j]+(j==tmp-1);
		}

이부분에서 j가 tmp-1일때 한번에 처리하는 방법을 모르겠어서,

for (int j = 0; j < 3; j++) {
			//cowInfo[i+1][tmp-1]은 i번째까지의 tmp-1에 해당하는 소의 갯수 
			//j가 tmp일때 ==연산자를 이용해 1 계산
			cowInfo[i + 1][j] = cowInfo[i][j];
            if(j==tmp-1) cowInfo[i + 1][j] +=1;
		}