백준 11969 자바 - Breed Counting (BOJ 11969 JAVA)

문제 : https://www.acmicpc.net/problem/11969

 

 

  breed 1,2,3에 각각 범위 내에 포함된 카운팅값의 합을 출력하면 된다. prefix sum을 활용하면 풀 수 있다. breed1,2,3로 나누어서 카운팅한 값의 누적합을 저장하는 방식으로 진행하면 된다.

 

  예제 입력1에 대해 그려보면 다음과 같다. N번 소에 대해 breed1,2,3를 사용했음을 기입한 것이다.

 

  이걸 breed 1,2,3에 대해 각각 누적합을 구해보면 다음과 같다.

 

  이렇게 전처리로 누적합을 구해두고, 각 쿼리의 a, b값에 대해 범위내의 합계를 출력해주면 된다. 예를들어 a=2, b=4라면 breed1의 경우 breed1[b] - breed1[a-1] = 2 - 0 = 2, breed2의 경우 마찬가지로 1 - 1 = 0, breed3의 경우 1 - 0 = 1 이다. 따라서 2 0 1 을 출력하면 된다.

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11900/BOJ_11969.java

import java.io.DataInputStream;
import java.io.IOException;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        int q = nextInt();

        int[][] sum = new int[n+1][3];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 3; j++)
                sum[i][j] = sum[i-1][j];
            sum[i][nextInt()-1]++;
        }

        StringBuilder sb = new StringBuilder();
        while (q-->0) {
            int a = nextInt();
            int b = nextInt();
            for (int j = 0; j < 3; j++)
                sb.append(sum[b][j]-sum[a-1][j]).append(' ');
            sb.append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}