[JAVA] 백준 20438 누적합

 

 

 

20438번: 출석체크

문제

지환이는 무작위로 한 명의 학생에게 출석 코드를 보내는 행위를 Q번 반복한 뒤, 출석부 정리를 위해 특정 구간의 입장 번호를 받은 학생들 중에서 출석이 되지 않은 학생들의 수를 구하고 싶다.

풀이

해당 문제는 먼저 출석이 안된 인원의 범위를 주고 해당 범위 안에 몇 명의 출석이 안된 인원이 있는지를 묻고 있다.

범위를 주고 해당 범위에 대한 값을 빠르게 구하기 위해서 누적합을 사용했다.

📌 졸고 있는 학생

        for(int i=0; i<K; i++){
            A[Integer.parseInt(st.nextToken())] = -1;
        }

졸고 있는 학생을 -1 값으로 체크해준다.

📌 출석

        for(int i=0; i<Q; i++){
            check(Integer.parseInt(st.nextToken()));
        }
    public static void check(int x){
        if(A[x] == -1) return;
        int times = 2;

        for(int i = x; i<A.length; i = x * times++){
            if(A[i] == 0){
                A[i] = 1;
                check(i);
            }
        }

    }

출석 체크를 받는 인원들은 check() 메서드를 통해서 자신의 다른 배수의 모든 학생들에게 출석을 보낸다.

• 만약 출석을 받은 학생이 -1 값이라면 종료한다.
• 만약 다음 출석을 받는 사람이 0값이 담겨 있다면 출석을 체크하고 해당 사람의 배수의 모든 학생들에게 출석을 보낸다.

📌 출석 체크되지 않은 사람들 수에 대한 누적합 배열

        int[] sum = new int[N+3];
        for(int i=3; i<sum.length; i++){
            sum[i] = sum[i-1] + (A[i] != 1 ? 1 : 0);
        }

이전 까지의 합 + A[i]의 값이 1이 아니라면 1을 더해준다.

• 0이거나 -1이라면 출석체크를 못한 인원이기 때문에 카운트해준다.

📌 출력

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(sum[b] - sum[a-1]).append("\n");
        }
        System.out.println(sb);

출력으로 합배열[b]( A[1] + A[2] .. ~ A[b]) - 합배열[a-1] (A[1] + A[2] + … + A[a-1])를 구해 범위에 대한 출석 못한 인원의 수를 StringBuilder에 담아 출력한다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        A= new int[N+3];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<K; i++){
            A[Integer.parseInt(st.nextToken())] = -1;
        }

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<Q; i++){
            check(Integer.parseInt(st.nextToken()));
        }

        int[] sum = new int[N+3];
        for(int i=3; i<sum.length; i++){
            sum[i] = sum[i-1] + (A[i] != 1 ? 1 : 0);
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(sum[b] - sum[a-1]).append("\n");
        }
        System.out.println(sb);

    }

    public static void check(int x){
        if(A[x] == -1) return;
        int times = 2;

        for(int i = x; i<A.length; i = x * times++){
            if(A[i] == 0){
                A[i] = 1;
                check(i);
            }
        }

    }

}

결과