[백준 13458] 시험감독

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

13458번: 시험 감독

#include <stdio.h>
int N;
int student[1000000 + 10];
int B, C;
long long int cnt;	//N = 1000000, 각 학생수 1000000, B = C = 1일 때 cnt = 1000000 * 1000000


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

void proctor(void)
{
	for (int i = 0; i < N; i++) {
		student[i] -= B;
		cnt++;
		if (student[i] > 0) {	//남아있는 학생의 수가 양수일때만 해주면 됨
			if (student[i] % C == 0) cnt += (student[i] / C);
			else cnt += ((student[i] / C) + 1);
		}
	}
}

int main(void)
{
	input();
	proctor();
	printf("%lld", cnt);
	return 0;
}

이거 AC 받고 나서 예전에 파이썬으로 푼거 보니까 코드가 왜이렇게 깔끔함....? 나참...

이 문제에서 중요했던 건 1. 루프의 횟수 2. cnt의 범위 이다. 

 

1. 루프는 한 번만 돌려야 한다. 

처음 풀때는 아무 생각없이 student[i] < 0 break; 조건 달고 무한루프 돌리면서 C를 빼주었다. 근데 이렇게 풀면 시간초과난다. 나누기 연산 하면 굳이 루프가 필요 없다.

//이렇게 짜면 타임아웃 난다
void proctor(void)
{
	for (int i = 0; i < N; i++) {
		student[i] -= B;
		cnt++;
		for (;;) {
			if (student[i] <= 0) break;
			student[i] -= C;
			cnt++;
		}
	}
}

 

2. cnt는 int 범위를 벗어날 수 도 있다. 

아... 진짜 C....는.... 타입의 범위까지 생각해줘야 하는 까다로운 언어라는 것을 ... 피부로 느꼈다.... 개오바...

이것도 아무생각 없이 int cnt; 이렇게 선언해주고 풀었는데, 만약 아래와 같은 경우 integer 범위를 벗어나게 된다.

input
1000,000
1000,000 1000,000 1000,000 ....... 1000,000
1 1

output
1000,000 * 1000,000	//int 범위 초과

ㅎ.. 그래서 cnt의 타입을 long long int로 선언해주고, 나중에 인쇄할 때도 printf("%lld", cnt); 이렇게 해주어야 통과된다.. 

진짜... 거지같.... 

 

 

추가적으로 테케에는 없지만 생각해야 하는 반례는 응시자의 수 보다 감독관이 감시할 수 있는 응시자가 더 많을 때 이다. 

아래와 같은 경우도 주의해서 문제를 풀어야 한다. 

input
1
1
5 1

output
1