[코테] 백준 그리디 14233번 문제

14233번 : 악덕 사장

문제 링크

https://www.acmicpc.net/problem/14233

문제 설명

남규회사를 운영하는 사장 zych는 직원들을 부려먹는 걸로 유명하다. 오늘도 zych는 직원들을 부려먹기 위해 고민을 하고 있다.

회사에 들어온 일들은 n개가 있고 각 일들의 마감기한이 있다. 일을 못하면 계약금을 물어야하기 때문에 모든 일을 해야 한다. 하지만 너무 적은 시간을 들이면 퀄리티가 낮아지므로 직원들을 굴려서 최대한 많은 시간을 일을 하게 하려한다. 하지만 또 일마다 시간이 다르면 직원들이 혼동을 하기에, 모든 일을 딱 k시간만 일을 하게 하려한다.

일들의 마감기한이 주어졌을 때, 모든 일을 하면서 k가 최대가 되는 값을 출력하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 첫째 줄에는 일의 개수 n이 주어진다.(1≤n≤50,000)

둘째 줄에는 각 일별로 마감기한 Ai가 주어진다.(1≤Ai≤1,000,000,000) 마감기한이 같은 입력은 들어오지 않는다.둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다.

출력

모든 일을 다 할 수 있는 일의 기한 최대 k를 출력하시오.

문제 풀이

N이 만약 4일 때 (1, 2, 3, 4), (2, 4, 6, 8), … 순으로 반복하면서 각 일의 마감기한보다 커질 때 반복문을 나간다.

N = int(input())
arr = sorted(list(map(int, input().split())))

for i in range(1, max(arr) + 1) :
    temp = list(range(i, N * i + 1, i)) 
        
    for j in range(N) :
        if temp[j] > arr[j] :
            i -= 1
            break
    else : 
        continue
    
    break
    
print(i)