BOJ 11969 - Breed Counting 링크
(2023.09.18 기준 S3)

문제

1~N의 번호를 가진 N마리의 소가 일렬로 세워져 있다.
각 소는 품종 1번, 2번, 아니면 3번 중 하나이다.

Q개의 구간 쿼리가 a, b 형태로 주어질 때마다 구간 [a, b]에 있는 각 품종마다 소의 수 출력

알고리즘

값의 변경이 없는 조건 하에 구간 합 쿼리를 처리해야 하므로 누적 합

풀이

결국 품종은 총 3가지인데, 각 품종마다 따로 구간 합 쿼리를 처리해야 하니깐 누적 합 배열을 3개 만들면 된다.

각 번호(위치)마다 해당하는 품종에 체크을 하고 누적 합 배열을 완성해서 구간 합 쿼리를 처리하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

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

    int N, Q; cin >> N >> Q;

    int cows[3][N + 1]; fill(&cows[0][0], &cows[2][N + 1], 0); // 각 번호마다 어떤 품종의 소인지 체크
    for (int i = 1, n; i <= N; i++){
        cin >> n;
        cows[n - 1][i] = 1;
    }

    // 품종 별로 누적 합 배열 만들기
    int prefix_sum[3][N + 1]; prefix_sum[0][0] = prefix_sum[1][0] = prefix_sum[2][0] = 0;
    for (int i = 0; i < 3; i++) for (int j = 1; j <= N; j++)
        prefix_sum[i][j] = prefix_sum[i][j - 1] + cows[i][j];
    
    // 구간이 주어질 때마다 품종 별로 몇 마리가 있는지 누적 합 배열을 이용하여 구하기
    for (int a, b; Q; Q--){
        cin >> a >> b;
        for (int i = 0; i < 3; i++) cout << prefix_sum[i][b] - prefix_sum[i][a - 1] << ' ';
        cout << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline

N, Q = map(int, input().split())

cows = [[0] * (N + 1) for _ in range(3)] # 각 번호마다 어떤 품종의 소인지 체크
for i in range(1, N + 1):
    cows[int(input()) - 1][i] = 1

# 품종 별로 누적 합 배열 만들기
prefix_sum = [[0] * (N + 1) for _ in range(3)]
for i in range(3):
    for j in range(1, N + 1):
        prefix_sum[i][j] = prefix_sum[i][j - 1] + cows[i][j]

# 구간이 주어질 때마다 품종 별로 몇 마리가 있는지 누적 합 배열을 이용하여 구하기
for _ in range(Q):
    a, b = map(int, input().split())
    for i in range(3):
        print(prefix_sum[i][b] - prefix_sum[i][a - 1], end = ' ')
    print()