문제

1. 자료형 int의 범위, 2. 부 감독관이 들어가는 경우

1. n 시험장의 수 (1 ≤ N ≤ 백만)

2. ai 시험장의 응시자의 수 (1 ≤ N ≤ 백만)

3. b 총 감독관이 감시할 수 있는 응시자의 수 (1 ≤ N ≤ 백만)

4. c 부 감독관이 감시할 수 있느 응시자의 수 (1 ≤ N ≤ 백만)

5. 각 시험장에는 총 감독관이 반드시 1명씩 꼭 들어갑니다.

6. 응시생을 모두 감독하기 위한 감독관의 최소 수

1. 첫인상

간단해 보인다. 쉬워 보인다. 그런데 입사문제가 너무 쉽다면, 다른것도 생각해봐야겠지

1) 유형

굳이 유형을 분류하자면, 다이나믹 프로그래밍이라고 생각합니다.

각 시험장의 최소 감독관의 수를 구하는 작은 문제를 풀면

전체를 감독하기 위한 감독관의 최소 수를 구할 수 있기 때문입니다.

2) 주의할 점

2가지가 있습니다.

1. 자료형 int의 범위
2. 부 감독관이 들어가는 경우

2. 자료형 int의 범위

int의 최대값은 2147483647 로 약 20억 입니다.

저는 보통 이일 사칠 사팔 삼육 사칠~ 로 리듬감있게 외웁니다.

만약, b=1, c=1, n=백만, ai=백만일경우

감독관의 총 수는 백만 * 백만 이 되어 1조가 됩니다. (정수 범위 초과)

• c, c++ - long long
• java - long
• python - 상관 없음

long long의 최대값은 9백경

외울 필요는 없고요, 보통 long long으로 안되는 경우는 문자열로 숫자를 입력받는 경우입니다.

3. 부 감독관이 들어가는 경우

부 감독관이 들어가는 경우는 주 감독관으로 부족해서 감시할 응시생이 남는 경우 입니다.

음, 그냥 하다보면 잊어버릴 수 있습니다.

if문을 통해 남은 응시생이 0보다 큰 경우 부 감독관을 계산해 줍시다.

4. 코드

1) c++

#include <iostream>
// 여유 있게 1을 붙여서 최대 숫자를 정의합니다.
#define max_int 1000001

/*
    정수 범위를 넘어가기 때문에 long long 을 사용합니다.
    int의 최대값은 2147483647 (20억)
    리듬감있게 외우면 외워집니다. 이일 사칠 사팔 삼육사칠~
 */

// long long을 편하게 쓰기 위해서 lld로 정의
#define lld long long

using namespace  std;

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 자료구조: 배열
    사용한 알고리즘: 반복문
 */

int n, a[max_int], b, c;
// 전체 감독관의 수는 정수 범위를 초과할 수 있기 때문에 long long으로 선언합니다.
lld result;

int main(){
    // 1. 입력
    scanf("%d", &n);

    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }

    scanf("%d %d", &b, &c);

    // 2. 계산
    for(int i=1; i<=n; i++){
        // 1) 총 감독관의 수
        // 총 감독관은 한반에 한명씩 꼭 들어갑니다.
        a[i] = a[i] - b;
        result++;

        // 2) 부 감독관의 수
        // 남은 응시생이 있어야 부 감독관이 들어갑니다.
        if(a[i] > 0) {
            // 나눗셈을 통해 부 감독관의 수를 계산합니다.
            result += a[i] / c;

            // 나머지가 있으면 부 감독관을 한명더 늘려줍니다.
            if(a[i] % c > 0) result++;
        }
    }

    // 3. 출력
    printf("%lld\n", result);
}

2) java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 자료구조: 배열
    사용한 알고리즘: 반복문
 */

public class Main {

    private static int n, b, c, a[];
    // 전체 감독관의 수는 정수 범위를 초과할 수 있기 때문에 long 으로 선언합니다.
    private static long result;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 1. 입력
        n = Integer.parseInt(br.readLine());
        a = new int[n+1];

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++){
            a[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        b = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        // 2. 계산
        for(int i=1; i<=n; i++){
            // 1) 총 감독관의 수
            // 총 감독관은 한반에 한명씩 꼭 들어갑니다.
            a[i] = a[i] - b;
            result++;

            // 2) 부 감독관의 수
            // 남은 응시생이 있어야 부 감독관이 들어갑니다.
            if(a[i] > 0) {
                // 나눗셈을 통해 부 감독관의 수를 계산합니다.
                result += a[i] / c;

                // 나머지가 있으면 부 감독관을 한명더 늘려줍니다.
                if(a[i] % c > 0) result++;
            }
        }

        System.out.println(result);
    }
}

3) python3

'''
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 자료구조: 배열
    사용한 알고리즘: 반복문
 '''
# 1. 입력
n = int(input())

a = list(map(int, input().split()))

b, c = map(int, input().split())

result = 0


# 2. 계산
for student in a:
    student = student - b
    result += 1

    if student > 0:
        result += student // c

        if student % c > 0:
            result += 1


print(result)