조각 크기
문제
한 연구실은 보관해 둔 기록 파일 K개를 외부 저장소로 옮기려고 한다. 파일의 크기는 파일마다 정해져 있으며 두 파일의 크기가 같을 수도 있다. 저장소는 파일을 조각 단위로 받는데, 보내는 조각은 모두 크기가 같아야 하고 조각의 크기는 자연수여야 한다.
조각을 만드는 방법은 다음과 같다. 파일 하나를 정해진 조각 크기로 앞에서부터 잘라 나가고, 조각 크기보다 작게 남은 끝부분은 버린다. 서로 다른 파일을 이어 붙여 한 조각을 만들 수는 없다. 그래서 어떤 파일에서 나오는 조각의 수는 그 파일의 크기를 조각 크기로 나눈 몫이다.
저장소에 보내야 하는 조각은 N개 이상이다. 조각을 크게 잡으면 파일마다 나오는 조각의 수가 줄어들므로, 연구실은 N개 이상을 만들 수 있는 범위에서 조각 하나의 크기를 가장 크게 잡으려고 한다. 주어지는 입력은 언제나 N개 이상의 조각을 만들 수 있는 경우다.
파일 K개의 크기와 필요한 조각의 수 N이 주어졌을 때, 만들 수 있는 조각 크기의 최댓값을 구하는 프로그램을 작성하여라.
예를 들어 K=4개의 파일 크기가 다음의 표와 같고, 필요한 조각의 수 N이 11이라고 해보자.
| 파일 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 크기 | 802 | 743 | 457 | 539 |
조각 크기를 200으로 잡으면 파일마다 나오는 조각의 수는 4개와 3개와 2개와 2개이고 모두 더하면 11개다. 필요한 11개를 채운다. 조각 크기를 201로 한 칸 올리면 3개와 3개와 2개와 2개가 되어 모두 10개이므로 11개를 채우지 못한다.
| 조각 크기 | 1번 | 2번 | 3번 | 4번 | 조각 수의 합 |
|---|---|---|---|---|---|
| 200 | 4 | 3 | 2 | 2 | 11 |
| 201 | 3 | 3 | 2 | 2 | 10 |
따라서 현재 예시에서 정답은 200이다. 조각 크기를 200으로 잡고 조각을 모두 떼어 내면 각 파일에서 2와 143과 57과 139만큼이 남는데, 이 남은 부분은 모두 버린다.
조각을 정확히 N개 만들어야 하는 것은 아니다. N개보다 많이 나오는 조각 크기라도 그 크기로 자를 수 있다.
입출력 예시
예시 1
입력
4 11 802 743 457 539
출력
200
예시 2
입력
2 108 471 173
출력
5
예시 3
입력
3 3 1 1 1
출력
1
입력 조건
가장 먼저 파일의 개수 K와 필요한 조각의 수 N이 첫째 줄에 공백 하나로 구분되어 차례대로 주어진다. K는 1 이상 10,000 이하의 자연수이고, N은 1 이상 1,000,000 이하의 자연수다.
이어서 둘째 줄부터 K+1번째 줄까지 각 파일의 크기가 한 줄에 하나씩 주어진다. 각 크기는 1 이상 2,147,483,647 이하의 자연수다. 주어지는 입력은 언제나 N개 이상의 조각을 만들 수 있는 경우다.
출력 조건
만들 수 있는 조각 크기의 최댓값을 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 보내는 조각은 모두 크기가 같아야 하고, 조각 크기는 자연수입니다
- 서로 다른 파일을 이어 붙여 한 조각을 만들 수는 없습니다. 조각 크기보다 작게 남은 끝부분은 버립니다
- 조각은 N개 이상 만들면 됩니다. 정확히 N개일 필요는 없습니다
- 파일의 크기는 2,147,483,647까지 올라갑니다. 어떤 파일에서 나오는 조각의 수는 크기를 조각 크기로 나눈 몫이며 나머지는 버립니다
- 입력은 언제나 N개 이상의 조각을 만들 수 있는 경우입니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 16개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 16개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 16개를 전부 통과해야 해결입니다.
2 108 471 173
5
4 11 802 743 457 539
200
3 3 1 1 1
1
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.