이 문제에서 고려해야할 것은 세가지로 요약할 수 있다.
1. Scanner vs BufferedReader -> 시간단축을 위해
2. 문제 조건에 따른 자료형 크기
3. 감독관수 최솟값을 구하는 알고리즘
1. Scanner vs BufferedReader -> 시간단축을 위해
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int countTestPlace = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] numOfPeople = new int[countTestPlace];
for (int a = 0; a < countTestPlace; a++) {
numOfPeople[a] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
int possFirstSupervi = Integer.parseInt(st.nextToken());
int possSecondSupervi = Integer.parseInt(st.nextToken());System.in => 콘솔로부터 데이터를 입력받는데 사용
InputStreamReader => 바이트 기반 스트림을 문자기반스트림으로 연결 시켜둔다.
BufferedReader => 버퍼를 이용해서 입출력의 효율을 높인다.
StringTokenizer => String을 공백 단위로 끊어주는 class
2. 문제 조건에 따른 자료형 크기
// 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성
long minSupervis = 0; // 3. 문제 조건에 따른 자료형 크기
먼저 출력할 정답인 필요한 감독수의 최솟값을 long타입으로 선언해 주었다.
왜 long type으로 선언해야할까?
예제를 다시보자
총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.
감독관은 총감독관과 부감독관으로 두 종류가 있다.
총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고,
부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.
각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.
각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.
셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)최대크기로 나올 수 있는 경우의 수를 생각해봤을때,
시험장 개수가 1,000,000일때와 각 시험장에 있는 응시자의 수가 1,000,000일때,
부감독관이 한 시험장에서 감시할 수 있는 응시자의 수가 1이라고
가정한다면, 필요한 감독수의 최솟값이 1,000,000 * 1,000,000이 된다.(총감독관 1명 제외)
1000000000000
1조
자료형의 크기를 다시 생각해보자
int형의 범위는 -2147483648 ~ 2147483647
long형의 범위는 -9223372036854775808 ~ 9223372036854775807
경우의 수에서 int형의 범위를 초과하기때문에, 정답을 long형으로 제출해야한다.
3.감독관수 최솟값을 구하는 알고리즘
for (int a = 0; a < countTestPlace; a++) {
numOfPeople[a] -= possFirstSupervi;
minSupervis++; // 총감독관 수 1명을 더해주고 넘어간다.
if (numOfPeople[a] <= 0) continue; // 0명 이하인 경우 패스
minSupervis += numOfPeople[a] / possSecondSupervi;
// 부감독관 수의 몫을 구해주고 최솟값에 더한다
if(numOfPeople[a] % possSecondSupervi > 0) {
// 부감독관 수로 나웠을때, 나머지가 0보다 크면 하나를 더해준다.
// 이렇게 하면 0.x명이 나왔을때, 1명을 더해줄 수 있다.
minSupervis++;
}
}
System.out.println(minSupervis);