[맛있는물회] [파이썬] <백준 알고리즘> <삼성기출문제> 13458번 "시험 감독"

문제 조건

---

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

 

Input

---

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

 

Output

---

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

 

생각한 아이디어

---

정답률이 25프로길래 좀 쫄았지만 그렇게 어려운 문제가 아니었다.

 

확실히 input 값 중에 범위가 백만 막 이렇게 주어지면 해결방법은 

<이분탐색 or  DP or 다익스트라..> 이렇게 압축되는 것 같다.

거의 큰 인풋값을 가진 대부분의 문제는 저런 해결방법으로 가능 한듯,.,,??

 

그래서 dp 느낌이 나길래 dp로 접근했다.

 

 

시험장에 들어간 사람들의 MAX 값까지 dp를 구현한다.

dp에는 필요한 감독관의 수가 들어간다.

맨첨에는 총감독관이 관리할 수 있는 사람 수 즉, A까지는 1로 초기화한다.

그 이후에는 하나씩 count하면서 부감독관이 관리할 수 있는 사람 수 B번 마다 증가값을 1씩 증가해주면서 dp를 초기화 해준다.

 

 

우선 주어진 조건대로 무조건 총감독관이 1명이 필요하다.

만약 총감독관이 가능한 수 A가 4, 부감독관이 가능한 수 B가 3일때 

시험장의 사람들이 A

dp

0 1 2 3 4 5 6 7 8 ... MAX [index]

1 1 1 1 1 2 2 2 3  [DP 함수]

 

이렇게 B만큼 count가 되면 하나더 더해주는 식으로 진행한다.

 

 

소스코드

import sys
import math
from collections import deque
import copy
input=sys.stdin.readline
INF=sys.maxsize

if __name__ == "__main__":
   n=int(input())
   arr=list(map(int,input().split()))
   b,c=map(int,input().split())
   MAX=max(arr)
   dp=[1]*(MAX+1)

   idx=1
   cnt=0
   for i in range(b+1,MAX+1):
      dp[i]+=idx
      cnt+=1
      if cnt==c:
         idx+=1
         cnt=0

   ans=0
   for i in range(0,n):
      ans+=dp[arr[i]]

   print(ans)

 

*파이썬 문법 정리