[백준/자바] 13458번: 시험 감독

문제

https://www.acmicpc.net/problem/13458

풀이

• N개 시험장 A
• i번 시험장 응시자 수 A[i]명
• 감독관: 총감독관, 부감독관
  • 총감독관: B명 감시
  • 부감독관: C명 감시
• 총감독관은 1명, 부감독관은 여러명 배치 가능
• 응시생을 모두 감시할 수 있는 최소 감독관의 수 출력

파이썬으로 풀어봤던 문제라 로직 자체는 크게 어렵지 않게 짰습니다.

그러나

틀렸습니다..
이유는 뒤에 보고 로직부터 작성해보겠습니다.

	public static long func() {
		long answer = n; // 시험장의 수만큼 ++
		for (int i = 0; i < n; i++) { // 모든 시험장 탐색
			a[i] -= b; // 총감독관이 감시하는 수 차감
			if (a[i] > 0) { // 총감독관이 감시할 수 있는 수를 초과할 경우
				if (a[i] % c == 0) { // 나누어 떨어지면
					answer += a[i] / c; // 부감독관이 감시할 수 있는 수만큼 배치
				} else {
					answer += a[i] / c + 1; // 나누어 떨어지지 않을 경우 부감독관이 감시할 수 있는 수 + 1만큼 배치
				}
			}
		}
		
		return answer;
	}

• 모든 시험장에는 총감독관 1명이 배치되어야 하기 때문에 answer에 n만큼 더해주었습니다.
• 시험장 전체를 탐색하며 총감독관이 감시할 수 있는 응시생의 수만큼 빼주었습니다.
  • 그래야 부감독관이 필요한지 안 필요한지 알 수 있으므로
• 만약 총감독관이 전체를 수용할 수 없으면 부감독관 배치
  • 부감독관이 감시할 수 있는 수로 나누어 떨어질 경우, 나눈 몫을 answer에 추가
  • 아니라면 나눈 몫 + 1만큼 추가

눈썰미가 좋으신 분들이라면 보셨겠지만, 리턴 값을 int가 아닌 long으로 선언했습니다.

문제를 잘 읽어보면

모든 값의 최댓값이 1,000,000(‼️)입니다.
만약, 시험장의 개수가 1,000,000, 응시자의 수가 모두 1,000,000이 된다면 최대 1,000,000,000,000가 나오게 되므로 int형에 모두 담을 수 없게 됩니다.
그러기 때문에 정답 값을 long으로 선언하지 않으면 틀렸다고 나오게 됩니다..

코드

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

public class Main_13458 {
	static int n;
	static int[] a;
	static int b, c;
	
	public static long func() {
		long answer = n;
		for (int i = 0; i < n; i++) {
			a[i] -= b;
			if (a[i] > 0) {
				if (a[i] % c == 0) {
					answer += a[i] / c; 
				} else {
					answer += a[i] / c + 1;
				}
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		b = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		System.out.println(func());
		
	}

}