백준 13458 : 시험 감독 (삼성 SW 역량테스트)_ C++

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

13458번: 시험 감독

 

#수학 #사칙연산 #bronze2

 

회고

 

✔ 시간 초과

문제 자체는 간단하여 테스트 케이스가 통과하는 코드는 굉장히 짧은 시간안에 작성할 수 있었다.

그러나 제출 해 보니 시간초과가 뜨길래 벡터를 사용해서 그런가? 싶어서 응시자 수를 저장하는 공간을 배열로 변경하였으나 역시나 똑같이 시간초과가 떴다.. (나중에 통과하고 난 후, 벡터를 사용해서 다시 채점해봤는데 맞았습니다가 뜬걸 통해 벡터의 문제가 아니었음을 다시한번 알게 되었다.)

 

고민해보니 부감독관 수를 구하는 while문에 문제가 있는것 같길래 while문을 사용하지 않는 방안을 찾아보았다.

기존에 내가 했던 방식은 뺄셈을 통해 구하는 방식이었는데 다시보니 무척이나 비효율적인 방법임을 깨닫게 되었고, 나누기를 통해 한번에 계산할 수 있다는 것을 알게되었다. (그리고 나머지가 생길 경우 부감독관을 if문을 통해 한번 더 추가해줬다.)

 

위의 방식을 선택하니 다행히 시간초과는 뜨지 않았지만 '틀렸습니다' 가 떠서 다른분들은 어떻게 해결했나 궁금하여 찾아보니 각 감독관이 한명씩만 감시 가능하다고 할 때, 시험장 수와 응시자 수가 최대일 경우(1조) int형의 범위(2147483647)를 가뿐하게 넘어버려서 그보다 더 큰 범위를 사용해줘야 하기 때문이었다.

따라서 cnt(감독관 총 수) 자료형을 int에서 long long으로 변경해주니 '맞았습니다' 가 떴다.

 

이 문제를 풀면서 시간과 자료형의 범위를 다시 한번 생각해 볼 수 있는 경험을 가질 수 있었다.

 

코드

 

with. 배열

#include <iostream>
#define MAX 1000010
using namespace std;

int n, b, c;
int arr[MAX];

int main() {
	cin >> n;
	int x;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cin >> b >> c;

	long long cnt = 0;
	for (int i = 0; i < n; i++) {
		int tmp = arr[i];
		tmp -= b;
		cnt++;
		if (tmp > 0) {
			cnt += tmp / c;
			if (tmp % c > 0) cnt++;
		}
	}
	cout << cnt;
	return 0;
}

with. 벡터

#include <iostream>
#include <vector>
using namespace std;

int n, b, c;
vector<int> v;

int main() {
	cin >> n;
	int x;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	cin >> b >> c;

	long long cnt = 0;
	while (!v.empty()) {
		int tmp = v.back();
		v.pop_back();
		tmp -= b;
		cnt++;
		
		if (tmp > 0) {
			cnt += tmp / c;
			if (tmp % c > 0) cnt++;
		}
	}
	cout << cnt;
	return 0;
}