백준 13458 시험 감독 자바로 풀어 본 짧은 글

13458번 문제 시험 감독

 

생각
범위는 전부 백만
첫째줄 시험장의 개수N입력받고
둘째줄N을 통해 for문돌려서 시험장에 있는 응시자 수 입력받고
셋째줄 B와 C를 배열0,1에 입력받음
이후 알고리즘이 들어간다.

 

-----

hint

총 시험응시자 수를 나눠 몫과 나머지를 활용한다. / 입력조건을 잘 보고 자료형을 고민해야함

 

 

-----

Solution

반응형

 

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        int N;
        int[] testCapa = new int[1000000];
        int[] supervisor = new int[2]; // 감독관
        int tmp;
        int remainder; // 나머지
        int quotient; // 몫
        long count = 0;
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt();
 
        for (int i = 0; i < N; i++) {
            testCapa[i] = sc.nextInt();
        }
 
        supervisor[0] = sc.nextInt(); // 총감독관
        supervisor[1] = sc.nextInt(); // 부감독관
 
        // 필요한 감독관 수의 최솟값을 만들기.
 
        for (int i = 0; i < N; i++) {
            tmp = testCapa[i];
            tmp -= supervisor[0];
            if (tmp < 1) { // tmp가 총감독관으로 끝날 때
                count++;
                continue;
            }
            else if (tmp > 0) { // tmp가 총감독관으로 안 끝날 때
                count++;
                remainder = tmp % supervisor[1];
                quotient = tmp / supervisor[1];
                
                count += quotient;
                
                if (remainder > 0) { // 나머지가 있으면 부감독관 한명 더 있어야함
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}
 

구현 자체는 오래 생각해서 그런지 쉽게 구현했고,
이번에도 너무 생각을 짧게 하고 구현했는지, 조건 부분에서 두번이나 틀렸었다.

1트 - count를 남발 중복적용으로 인해 오답
2트 - 똑같이 조건이 아쉬움 count가 잘못적용됨
3트 - 모든 예제가 맞게끔 잘 적용 되었는데 자꾸틀림 질문게시판의 반례도 찾아봤지만, 모든 반례가 맞음
4트 - 바보같은 실수를 한 것을 깨달았음... 카운트 횟수는 100만*100만으로 int형의 42억으로는 감당을 하지 못해서 에러가 난 것이였음. 이후 count변수의 자료형을 long으로 변경 후 정답
실행시간 - 1712ms ///정답율 28.2%인게 다들 똑같은 실수 한거같음....

 

 

			if (tmp < 1) { // tmp가 총감독관으로 끝날 때
				count++;
				continue;
			}

5트 - 시간이 너무 오래걸림... 최대 100만번 for문을 돌리니 그럴 수밖에 없던 문제인듯함

때문에 조건을 달았었음 총 감독관으로 해당 시험장이 끝난다면 바로 종료되게끔 continue문을 넣어서 실행해봄 1712에서 아주아주 약간 줄었음.
실행시간 - 1688ms

 

그냥 내 효율적이지 못한 알고리즘이 문제인거 같다....
일단 구현에는 성공했으니 찝찝한 기분 안아두고 킵
당장 생각할 수 있는거는 BufferReader밖에 없는데 그거하나 넣는다고 드라마틱하게 바뀔거 같지 않음