백준 20438번: 출석체크

문제 설명

• https://www.acmicpc.net/problem/20438

접근법

• 코드를 전달받았는지 여부를 나타내는 v배열을 먼저 작성한 뒤, 누적합을 계산하기 위한 cumSum배열을 활용했습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		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());

		boolean[] v = new boolean[N + 3];
		List<Integer> SleepStudent = new ArrayList<Integer>();
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < K; i++) {
			SleepStudent.add(Integer.parseInt(st.nextToken()));
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < Q; i++) {
			int now = Integer.parseInt(st.nextToken());
			if(SleepStudent.contains(now)) continue;
			if (!v[now]) {
				for (int j = now; j < N + 3; j++) {
					if (j % now == 0) {
						if (!SleepStudent.contains(j)) {
							v[j] = true;
						}
					}
				}
			}
		}

		int[] cumSum = new int[N + 3];
		for (int i = 3; i < cumSum.length; i++) {
			cumSum[i] = cumSum[i - 1] + ((!v[i]) ? 1 : 0);
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			System.out.println(cumSum[e] - cumSum[s - 1]);
		}

	}

}