- 자료형 int의 범위, 2. 부 감독관이 들어가는 경우
n 시험장의 수 (1 ≤ N ≤ 백만)
ai 시험장의 응시자의 수 (1 ≤ N ≤ 백만)
b 총 감독관이 감시할 수 있는 응시자의 수 (1 ≤ N ≤ 백만)
c 부 감독관이 감시할 수 있느 응시자의 수 (1 ≤ N ≤ 백만)
각 시험장에는 총 감독관이 반드시 1명씩 꼭 들어갑니다.
응시생을 모두 감독하기 위한 감독관의 최소 수
간단해 보인다. 쉬워 보인다. 그런데 입사문제가 너무 쉽다면, 다른것도 생각해봐야겠지
굳이 유형을 분류하자면, 다이나믹 프로그래밍이라고 생각합니다.
각 시험장의 최소 감독관의 수를 구하는 작은 문제를 풀면
전체를 감독하기 위한 감독관의 최소 수를 구할 수 있기 때문입니다.
2가지가 있습니다.
int의 최대값은 2147483647 로 약 20억 입니다.
저는 보통 이일 사칠 사팔 삼육 사칠~ 로 리듬감있게 외웁니다.
만약, b=1, c=1, n=백만, ai=백만일경우
감독관의 총 수는 백만 * 백만 이 되어 1조가 됩니다. (정수 범위 초과)
long long의 최대값은 9백경
외울 필요는 없고요, 보통 long long으로 안되는 경우는 문자열로 숫자를 입력받는 경우입니다.
부 감독관이 들어가는 경우는 주 감독관으로 부족해서 감시할 응시생이 남는 경우 입니다.
음, 그냥 하다보면 잊어버릴 수 있습니다.
if문을 통해 남은 응시생이 0보다 큰 경우 부 감독관을 계산해 줍시다.
#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);
}
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);
}
}
'''
시간 복잡도: 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)