[Baekjoon] 11969_Breed Counting

문제(출처: https://www.acmicpc.net/problem/11969)

---

< Breed Counting >

 

문제 풀이 

 

특정 구간에 포함된 각 품종의 소가 몇 마리인지 구하는 것이므로 누적합을 사용한다. 

주어진 예제를 푸는 방법은 다음과 같다.

6 3
2          -> [0,1,0]
1          -> [1,1,0]      
1          -> [2,1,0]
3          -> [2,1,1]
2          -> [2,2,1]
1          -> [3,2,1]
1 6       => 전체 구간이므로 [3,2,1]
3 3       => [2,1,0] - [1,1,0] = [1,0,0]
2 4       => [2,1,1] - [0,1,0] = [2,0,1]

 

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _11969_ { // Breed Counting

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());

		int cow[][] = new int[n + 1][3];

		for (int i = 1; i <= n; i++) {
			int id = Integer.parseInt(bf.readLine()) - 1;

			for (int j = 0; j < 3; j++) {
				cow[i][j] = cow[i - 1][j];
			}

			cow[i][id] += 1;
		}

		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(bf.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			for (int j = 0; j < 3; j++) {
				bw.write(cow[b][j] - cow[a - 1][j] + " ");
			}
			bw.write("\n");
		}
		bw.flush();
	}
}

변수)
n : 소의 수
q : 특정 구간 개수
cow : 소의 누적 합
a, b : 특정 구간

 

소의 수와 특정 구간 개수를 입력받는다. 소의 수만큼 품종 ID를 입력받아 cow 배열에 누적합을 저장한다. 특정 구간 개수만큼 특정 구간을 입력받아 배열 [b] - [a-1] 값을 구해 출력한다.

---

---