[백준 -13458번] 시험감독 - JAVA 정리 및 해설 (삼성 SW 역량테스트 문제)

이번 문제는 삼성 SW 역량 테스트에서 출제한 문제들을 모아서 한번에 정리하려고 합니다.

첫번째는 제가 생각하기에는 가장 쉬운 문제인 시험 감독입니다. 

올려도 보는 사람은 없겠지만, 삼성문제에 대해서 정리도 필요하고, 한 번쯤은 정리해보는 시간이 필요할 것 같아서 역량테스트 문제끼리 묶어서 같이 공부하려고 시작을 했습니다. 

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

이 문제는 사실 특별하게 "구현"을 하지 않아도 답을 대략적으로 유추할 수 있는 계산 값이 나옵니다. 

일단 문제의 조건을 확인을 해보죠. 첫째로, 시험 감독은 각 시험 감독이 최대로 볼 수 있는 수험생의 수는 정해져있습니다.

둘째로, 시험 총감독은 무조건 한명만 필요하고 부 감독은 여러명이든 없든 상관이 없으니 그 학생의 수를 충족해 줘야 합니다. 

그럼 이걸 계산하는 방식은 진짜로 단순한 겁니다. 

각 방에서 총감독의 인원수를 빼고, 부감독을 인원수가 -가 되는 순간까지 빼주고 그 감독의 총 인원수를  카운트 시키면 되는 단순한 문제라는 거죠.

이런 방식은 심지어, 시간 복잡도를 계산을 하지 않아도 될정도로 작고( 기껏해야 1,000,000정도 밖에 안되서) 루프를 돌아도 백만바퀴 밖에 안돌게되니, 크게 신경 안써도 된다는 거죠.

그럼 코드를 한번 만들어보죠.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int a = Integer.parseInt(br.readLine());
		String student = br.readLine();
		StringTokenizer st = new StringTokenizer(student, " ");
		int room [] = new int[a];
		String bc = br.readLine();
		StringTokenizer st1 = new StringTokenizer(bc, " ");
		int b = Integer.parseInt(st1.nextToken());
		int c = Integer.parseInt(st1.nextToken());
		int num = 0;
		for(int i=0; i<a; i++){
			room[i] = Integer.parseInt(st.nextToken());
			room[i] -= b;
			num++;
			if(room[i] / c==0 &&room[i]%c>0){
				num+= (room[i] / c)+1;
			}
			if(room[i] / c!=0&&room[i]%c>0){
				num+= (room[i] / c)+1;
			}
			if(room[i] / c!=0&&room[i]%c==0){
				num+= (room[i] / c);
			}
			
		}
		System.out.println(num);
		
	}
}

 

이러면 답이 안나오게 되는데 뭐가 문젤까요? 

두가지 요인이 있긴 있는데 일단 기본적으로 백만이라는 조건 덕분에 num (즉, 답)을 도중에 꼬일수도  있으므로, 

예를 들면 감독관이 볼 수 있는 명수가 1명 밖에 없다던가 이런 경우가 되면 결국 int 범위를 초과하기 때문에 주의 해야합니다.

"LONG"으로 만드는 것이 중요합니다. int가 가진 수의 범위를 초과할 수 있으므로, 조심해야합니다. 두번째 요인은 밑에 정답코드를 보고 확인 해보시죠.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int a = Integer.parseInt(br.readLine());
		String student = br.readLine();
		StringTokenizer st = new StringTokenizer(student, " ");
		int room [] = new int[a];
		String bc = br.readLine();
		StringTokenizer st1 = new StringTokenizer(bc, " ");
		int b = Integer.parseInt(st1.nextToken());
		int c = Integer.parseInt(st1.nextToken());
		long num = 0;
		for(int i=0; i<a; i++){
			room[i] = Integer.parseInt(st.nextToken());
			room[i] -= b;
			num++;
			// room이 음수일때도 결국 빠지게 되는데?
			if(room[i]>=0){
				if(room[i]/c==0 && room[i]%c>0){
				num+= (room[i] / c)+1;
				}
				if(room[i]/c!=0 && room[i]%c>0){
				num+= (room[i] / c)+1;
				}
				if(room[i] / c!=0&&room[i]%c==0){
				num+= (room[i] / c);
				}
			}
			
		}
		System.out.println(num);
		
	}
}

 

치명적인 실수는 총감독의 인원수에서 학생수를 뺐을때 음수가 나오면 빼줄 필요가 없는데, 전의 코드는 빼준다는 사실에 있습니다. 

테스트케이스중에 아마 총감독의 인원수가 총인원수보다 많은 경우가 있어서 부감독을 빼줄 필요가 없는 경우에서 더 빼줘서 인원수가 더 추가되서 문제가 발생한 것 같은데,  그런 점만 조심하면 문제 없이 풀 수 있을 겁니다.

다음편은 테트로미노로 돌아오겠습니다. 

https://sundries-in-myidea.tistory.com/7 테트로미노 문제