백준 13458 시험 감독 C++

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

13458번: 시험 감독

 

최종 코드

• GitHub https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ13458.cpp

hwayeon351/BEAKJOON-Algorithms

//
//  main.cpp
//  BJ13458
//
//  Created by Hwayeon on 2021/06/30.
//

#include <iostream>
using namespace std;

int N, B, C;
int p[1000000] = {0,};
long long ans = 0;

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> p[i];
    }
    cin >> B >> C;
    
    for(int i=0; i<N; i++){
        int num_c = p[i]-B;
        if(num_c <= 0) ans ++;
        else if(num_c % C!=0){
            int num_bc = 2+num_c/C;
            ans += num_bc;
        }
        else{
            int num_bc = 1+num_c/C;
            ans += num_bc;
        }
    }
    cout << ans << endl;
    
    return 0;
}

---

 

풀이 과정

풀이 시간 25분

이 문제에서 유의해야 할 점이 두 가지 있었다.

하나는 정답의 자료형을 long long으로 선언해야 하고, 하나는 각각의 시험장에 총감독관은 무조건 한 명이 있어야 한다는 점이다.

문제에서는 애매하게 '각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.'라고 해서 캐치하지 못했는데, 실제 시험장에는 총감독관이 무조건 배치된다는 점과 예제 문제를 통해서 유추할 수 있었다.

처음에 ans의 자료형을 int로 선언하는 바람에 예제 문제는 모두 통과하였지만, 제출하니 시작부터 틀렸습니다가 나왔다.

입력 조건을 살펴보면 최대 시험장의 개수는 1,000,000이고, 각 시험장의 최대 응시자 수는 1,000,000이다.

최대 경우를 따져보면 B=1, C=1인 경우, 각 시험장의 최소 감독관 수는 1,000,000명이기 때문에 총 감독관 수는 1,000,000x1,000,000 = 10^12명이 된다.

int형의 범위는 -2,147,483,648 ~ 2,147,483,647이기 때문에 최대 경우를 담지 못한다.

따라서 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 범위의 데이터를 표현할 수 있는 long long 자료형을 사용해야 한다.

초기에 변수를 선언할 때, 최대값과 최솟값을 고려해서 자료형을 선택하도록 늘 주의해야겠다.

//
//  main.cpp
//  BJ13458
//
//  Created by Hwayeon on 2021/06/30.
//

#include <iostream>
using namespace std;

int N, B, C;
int p[1000000] = {0,};

//최대 감독 수 = 10^12
//int -> 10^9
//long long -> 10^18
long long ans = 0;

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> p[i];
    }
    cin >> B >> C;
    
    for(int i=0; i<N; i++){
    	//부감독관이 감독해야 하는 시험자 수
        int num_c = p[i]-B;
        
        //총감독관만 필요한 경우
        if(num_c <= 0) ans ++;
        
        //부감독관도 필요한 경우
        else if(num_c % C!=0){
            int num_bc = 2+num_c/C;
            ans += num_bc;
        }
        else{
            int num_bc = 1+num_c/C;
            ans += num_bc;
        }
    }
    cout << ans << endl;
    
    return 0;
}

#시간복잡도 = O(n), 공간복잡도 = O(n)