BOJ - 13458 ) 시험감독

---

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

13458번: 시험 감독

 

---

N개의 방에 필요한 최소 시험감독의 수를 구하는 문제이다.

 

무조건 i번째 방에는 1 명의 총감독이 필요하므로 총감독이 감독할 수 있는 시험자의 수를 제외하고

 

나머지 사람들을 부감독이 감시할 수 있는 사람의 수로 나누어서 부감독의 사람수를 구한다.

 

간단한 메모제이션을 통하여, 이전에 구했던 시험자 수에대해서 다시구하지 않도록 처리해주자.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int max = 1000001;
		int N = Integer.parseInt(st.nextToken());
		int person[] = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int index = 0 ; index < N ;index++) person[index] = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int B = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int Memo[] = new int[max];
		long answer= 0;
		int cnt=1; 
		for(int index = 0 ; index < N ; index++) {
			if(Memo[person[index]]!=0) {
				answer +=Memo[person[index]];
				continue;
			}
			cnt=1;
			if(person[index]-B > 0) {
				cnt +=((person[index]-B)/C);
				if((person[index]-B)%C != 0 ) cnt++;
			}
			Memo[person[index]] = cnt; 
			answer += cnt;
		}
		
		System.out.println(answer);
		
	}
}

---