[Algorithm] BOJ 13458 : 시험 감독

 

 

안녕하세요 iOS 개발하는 루피입니다.

 

오늘은 백준 13458번 시험 감독 문제를 풀어 보았습니다. 삼성 기출 문제를 풀던 와중 등급이 낮아 쉽게 성공할 줄 알았지만, 예상외로 그렇지 못해 블로그에 작성해보려 합니다.

첫 접근 방법

• 처음 총 감독관이 감시할 수 있는 학생수를 제외하고, 필요한 감독관 수를 증가시킨다.
• 나머지 학생수를 부 감독관이 감시할 수 있는 학생 수 만큼 계속 빼고, 이때 필요한 감독관 수를 증가시킨다.

이렇게 작성하니 지속적으로 학생수를 빼야 하기에 시간 초과가 났습니다. 브론즈 문제라 사실 시간 초과를 신경 쓰지 않았지만, 이번 기회에 한번 메모리 제한을 생각해야겠다는 생각을 하였습니다.

두 번째 접근 방법

• 시간 초과의 원인을 For문을 통한 뺄셈으로 파악했습니다.
• 이를 나누기 방식으로 바꾸고 문제를 풀어 나갔습니다.

그러니깐 이번에는 틀렸다고 뜨더라고요 솔직히 틀릴 줄 몰랐는데 생각보다 케이스를 고려하지 못했던 거 같습니다.

마지막 접근 방법

• 처음 총 감독관이 감시할 수 있는 학생 수를 제외하고 나서 이후에 if 문으로 case를 나누었으나, 이때 나머지가 발생하는 case를 고려하지 않았습니다. 따라서 이번에는 나머지가 발생하는 경우와 발생하지 않은 경우를 나누고 이에 맞는 수식을 넣었습니다.

그러자 결과는 SUCESS 였습니다.

전체 코드

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    long long testCase; cin >> testCase;
    vector<long long>v(testCase);
    
    for( long long i=0;i<testCase;i++) {
        cin >> v[i];
    }
    
    long long B,C; cin >> B >> C;
    long long cnt = 0;
    
    for( long long i=0; i<v.size(); i++){
        v[i] -= B; cnt++;
         
        if(v[i] > C){
            long long k = v[i] / C;
            
            // 나머지가 있거나 없는 경우 Case 분류
            if(v[i] % C != 0){
                cnt += k+1;
            } else {
                cnt += k;
            }
        }
        
        else if(v[i] >0 && v[i] <= C) {
            cnt++;
        }
    }
    cout << cnt <<"\n";
}

새로운 방식

제가 나머지를 처리하는 방식에서 단순히 케이스 따라 +1하는 방식으로 문제를 접근했지만, 이보다 훨씬 더 간편한 방식이 있었습니다.

 for (long long i = 0; i < v.size(); i++) {
        // 총감독관이 각 시험장에 배치되어야 함
        v[i] -= B; 
        cnt++;
        
        // 남은 학생이 있다면 부감독관이 필요함
        if (v[i] > 0) {
            cnt += (v[i] + C - 1) / C; // 나머지가 발생할 경우 올림 계산이 가능합니다.
        }
    }

이런 식으로 총감독관이 감독할 수 있는 인원을 빼고 나서 한 번에 올림을 계산하는 방식을 이용한다면, 케이스를 분류하는데 힘을 덜 쓸 수 있다네요. 저는 저렇게 올림 계산 방식을 사용하지 않아 새로운 방식이었습니다!! 다음에는 한번 꼭 써먹어보도록 하겠습니다!