BOJ 13458 : 시험 감독 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/13458

 

먼저 총감독관은 1명이어야 하므로 각 응시자수에서 B만큼 뺀다.

그리고 남은 응시자들을 감독할 부감독관을 계산하면 된다.

 

따라서 sum = 총감독관 (N명) + 부감독관 수가 된다.

응시자 수가 적어서(A[i] <= 0) 총감독관으로 모두 커버 가능하면 부감독관을 계산할 필요가 없다.

 

부감독관의 수는 (A[i] - 1) / C + 1이 되는데, 아래의 경우를 생각해보자.

 

부감독관이 감시 가능한 수가 3일 때,

 

남은 학생 수 1 => 1명 필요

남은 학생 수 2 => 1명 필요

남은 학생 수 3 => 1명 필요

남은 학생 수 4 => 2명 필요

...

 

즉 감시 가능한 수의 배수 + 1 일 때, 부감독관이 1명 증가한다는 것을 알 수 있다.

따라서 총원에서 1을 빼주고 C 만큼 나눈 다음 1을 더하면 총 부감독관의 수가 된다.

#include <stdio.h>

#define MAX (1000000 + 50000)

typedef unsigned long long int ull;

int N;
int A[MAX];
int B, C;

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", &A[i]);

	scanf("%d %d", &B, &C);
}

int main(void)
{
	input();
	ull sum;

	sum = 0;
	for (int i = 0; i < N; i++) A[i] -= B; /* 총감독관이 감시 */

	sum += N;

	for (int i = 0; i < N; i++)
	{
		if (A[i] > 0) /* 총감독관이 모두 감시 가능 */
		{
			sum += (A[i] - 1) / C + 1;
		}
	}

	printf("%llu\n", sum);

	return 0;
}

 

간단한 수학 문제지만, 조금 치사한 점은 sum을 int로 하면 틀린다는 것이다.

(실제 시험장에서 overflow tc가 제공되었는지는 모르겠다.)

 

시험장에 들어가기 전에 type에 유의해야 한다는 점을 환기하기 위한 문제인 듯.

 

문제를 보면 답이 int 범위를 넘을 수 있는데, 제공하는 tc에 이런 경우가 없다면, 알아내기 힘들다.

 

typedef를 이용하면 길이가 긴 type을 편하게 줄일 수 있다.

 

마찬가지로, A형은 tc가 여러 개 이므로 초기화하는 코드도 추가해두도록 하자.

int main(void)
{
	int T;
	scanf("%d", &T);

	for (int tc = 1; tc <= T; tc++)
	{
    	input(); 
    	
     	ull sum = 0;
        
        ...
    	
		printf("#%d %llu\n", tc, sum);
	}
    
    return 0;
}