[Math] 바이러스 검사 - 삼성전자
바이러스 검사를 식당마다 올림 나눗셈으로 계산해 푼 기록입니다. 팀장 한 명이 강제라는 조건을 식에 넣는 자리와 답이 int를 넘는 이유를 정리합니다.
문제
바이러스의 확산을 막기 위해 총 n개의 식당에 있는 고객들의 체온을 측정하고자 합니다. 체온을 측정하는 검사자는 검사팀장과 검사팀원으로 나뉘어집니다. 팀장과 팀원이 검사할 수 있는 고객의 수가 다르며, 한 가게당 팀장은 오직 한 명, 팀원은 여러명 있을 수 있습니다. 하지만 가게당 팀장 한 명은 무조건 필요합니다. 가게에 검사팀원만 존재하는 경우는 있을 수 없습니다. 팀장이든 팀원이든 담당한 가게에 대해서만 검사합니다.
n개의 식당 고객들의 체온을 측정하기 위해 필요한 검사자 수의 최솟값을 구하는 프로그램을 작성해주세요.
입력
첫째 줄에는 식당의 수를 의미하는 정수 n이 주어집니다.
둘째 줄에는 각 식당에 있는 고객의 수가 공백을 사이에 두고 주어집니다.
셋째줄에는 검사팀장이 검사할 수 있는 최대 고객 수와 검사팀원이 검사할 수 있는 최대 고객 수가 공백을 사이에 두고 주어집니다.
제한 조건
- 1 ≤ n ≤ 1,000,000
- 1 ≤ 각 식당에 있는 고객의 수 ≤ 1,000,000
- 1 ≤ 팀장 혹은 팀원 한 명이 검사 가능한 최대 고객의 수 ≤ 1,000,000
- 모든 고객 수는 정수입니다.
출력
n개의 식당의 고객들을 모두 검사하기 위한 검사자의 최소의 수를 출력하세요
입력 예제
예제 1
1
2
3
1
1
2 2
1
1
예제 설명입니다. 밑의 그림에서 REST은 식당, CUST는 고객, LDR은 검사 팀장, MBR은 검사 팀원 입니다.
하나의 식당에 한 명의 손님이 있고, 팀장 한 명이 검사를 진행하면 되므로, 총 필요한 검사자는 1명 입니다.
예제 2
1
2
3
5
999999 999999 999999 999999 999999
111111 5
1
888895
예제 설명입니다. 5개의 식당에 각 999999명의 손님이 있습니다. 각 식당마다, 팀장 한 명이 111111명을 검사하고, 팀원들이 한 명당 5명씩 총 888888명의 손님을 검사해야 합니다. 팀원 177777명이 5명씩 검사하고, 1명의 팀원이 3명만 검사하면 되므로, 필요한 팀원은 177777 + 1 = 177778명 입니다. 그러므로, 하나의 식당에 필요한 총 검사자는 1 + 177778 = 177779명 이고, 5개의 식당에 필요한 검사자는 177779 x 5 = 888895명 입니다.
예제 3
1
2
3
3
10 15 13
7 14
1
6
예제 설명입니다. 3개의 식당에 각 10명, 15명, 13명의 손님이 있습니다. 각 식당에서, 팀장이 7명의 사람을 검사하고, 남은 사람들은 한 명의 팀원이 검사할 수 있으므로, 하나의 식당에는 2명의 검사자가 필요합니다. 그러므로 필요한 총 검사자는 2 x 3 = 6명 입니다.
힌트
답의 범위가 10^12 까지 커질 수 있는 문제입니다. C/C++/Java에서의 int형의 경우 2^31 - 1 까지만 값 표현이 가능하므로 언어별로 다른 자료형을 사용하셔야 합니다.
(1) C
int대신 long long 타입을, 포맷에서는 %d 대신 %lld를 사용해주세요.
(2) C++
int대신 long long 타입을 사용해주세요.
(3) Java
int대신 long 타입을 사용해주세요.
제한
- Time Limit: 1000 ms
- Memory Limit: 220 MiB
발상
여기는 직접 적습니다. 아래 셋을 채웁니다.
- 문제를 무엇으로 바꿔 읽었는지
- 먼저 떠오른 방법과 그것이 왜 안 되는지. 입력 크기를 근거로
- 그래서 무엇을 골랐고 왜 그것이면 되는지
풀이
제출한 코드입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
N = int(input())
guest = list(map(int,input().split()))
leader_max, member_min = list(map(int,input().split()))
for i in range(N):
guest[i] -= leader_max
answer = 0
for i in range(N):
if ( guest[i] > 0 ):
answer += (guest[i] + member_min-1) //member_min
print(answer+N)
팀장 한 명이 무조건 필요하다는 조건이 두 자리에 나뉘어 들어가 있습니다. 첫 번째 반복에서 guest[i] -= leader_max 로 팀장이 맡을 몫을 미리 빼 두고, 마지막 줄의 answer + N 에서 식당 수 N을 그대로 더합니다. 식당마다 팀장이 정확히 한 명이므로 팀장 수의 합은 N입니다.
guest[i] 가 0 이하이면 팀장 혼자로 끝나므로 팀원을 세지 않습니다. 0보다 크면 남은 인원을 팀원 한 명당 member_min 명씩 나눠 맡습니다. (guest[i] + member_min - 1) // member_min 이 올림 나눗셈입니다. 마지막 팀원이 정원을 다 채우지 못해도 한 명은 필요하기 때문에 내림이 아니라 올림입니다.
예제 세 개를 넣은 결과입니다.
1
2
3
1
1
2 2
1
1
1
2
3
5
999999 999999 999999 999999 999999
111111 5
1
888895
1
2
3
3
10 15 13
7 14
1
6
복잡도
| 구분 | 값 |
|---|---|
| 입력 크기 | 1 ≤ n ≤ 1,000,000, 고객 수와 검사 가능 인원 각각 1 이상 1,000,000 이하 |
| 시간 | O(n) |
| 공간 | O(n) |
시간이 O(n)인 이유는 식당을 두 번 훑고 각 식당에서 하는 일이 뺄셈 한 번과 나눗셈 한 번으로 고정이기 때문입니다. 식당끼리 영향을 주고받지 않아서 정렬이나 탐색이 필요 없습니다.
공간이 O(n)인 이유는 둘째 줄을 통째로 리스트에 담기 때문입니다. 한 줄에 최대 100만 개의 정수가 들어옵니다. 값을 읽으면서 바로 더하면 O(1)로 줄일 수 있지만 제출한 코드는 리스트를 만듭니다.
이 복잡도로 제한 안에 드는 근거입니다. n = 1,000,000에 고객 수를 1부터 1,000,000 사이에서 무작위로 채우고 팀장과 팀원의 정원을 각각 1로 둔 입력을 만들어 돌려 보니 파이썬 3.14에서 0.35초가 걸렸습니다. 시간 제한 1000ms 안에 듭니다. 채점 결과는 319ms였습니다.
답의 크기도 봅니다. 식당 100만 개에 각각 고객이 100만 명이고 팀장과 팀원이 한 명씩만 맡을 수 있으면 검사자는 10^12명입니다. 파이썬은 정수 크기에 제한이 없어서 그냥 넘어가지만, 문제의 힌트가 짚은 대로 C나 자바로 풀면 이 자리에서 int가 넘칩니다.