[Algorithm] 삼성 SW 역량테스트 2015 하반기 1번 문제 바이러스 검사, 코드트리 | 파이썬 (그리디)

※ 바이러스 검사

https://www.codetree.ai/training-field/frequent-problems/problems/virus-detector/description?page=1&pageSize=20&name=%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제]

바이러스의 확산을 막기 위해 총 n개의 식당에 있는 고객들의 체온을 측정하고자 합니다. 체온을 측정하는 검사자는 검사팀장과 검사팀원으로 나뉘어집니다. 팀장과 팀원이 검사할 수 있는 고객의 수가 다르며, 한 가게당 팀장은 오직 한 명, 팀원은 여러명 있을 수 있습니다. 하지만 가게당 팀장 한 명은 무조건 필요합니다. 가게에 검사팀원만 존재하는 경우는 있을 수 없습니다. 팀장이든 팀원이든 담당한 가게에 대해서만 검사합니다.

n개의 식당 고객들의 체온을 측정하기 위해 필요한 검사자 수의 최솟값을 구하는 프로그램을 작성해주세요.

 

[입력 조건]

첫째 줄에는 식당의 수 n이 주어집니다.

둘째 줄에는 각 식당에 있는 고객의 수가 공백을 사이에 두고 주어집니다.

셋째줄에는 검사팀장이 검사할 수 있는 최대 고객 수와 검사팀원이 검사할 수 있는 최대 고객 수가 공백을 사이에 두고 주어집니다.

• 1 ≤ n ≤ 1,000,000
• 1 ≤ (각 식당에 있는 고객의 수) ≤ 1,000,000
• 1 ≤ (팀장 혹은 팀원 한 명이 검사 가능한 최대 고객의 수) ≤ 1,000,000

[출력 조건]

n개의 식당의 고객들을 모두 검사하기 위한 검사자의 최소의 수를 출력하세요

[입력 예시1]

1

1

2 2

[출력 예시1]

1

[입력 예시2]

5

999999 999999 999999 999999 999999

111111 5

[출력 예시2]

888895

[입력 예시3]

3

10 15 13

7 14

[출력 예시3]

6

 

문제 해결 TIP

우선 가게당 팀장 한 명씩은 있어야 하니, 팀장이 맡을 수 있는 고객의 수를 모두 한번씩 빼준다. 이후 남은 고객 수를 팀원이 맡을 수 있는 수로 나누어주어, 몇 명의 팀원이 필요한지 계산한다. 이때 주의해야 할 점은 팀장이 맡은 후에 고객의 수가 0보다 작거나 같을때 넘겨야 한다는 것이다.

 

 

전체 코드

n = int(input())
people = list(map(int,input().split()))
leader, member = map(int,input().split())
#people = [10,15,13]

for i in range(len(people)):
    people[i] -= leader
#people = [3,8,6]
answer = 1*n

for i in range(len(people)):
    if people[i] <= 0:
        continue
    if people[i] % member == 0:
        answer += int(people[i]/member)
    else:
        answer += int(people[i]/member)+1
print(answer)