책장 나누기
문제
어느 마을 도서관이 책 N권을 기증받았다. 사서는 이 책을 책장 K개에 모두 꽂아야 한다.
꽂을 때 지켜야 하는 규칙이 두 가지 있다. 첫째, 책장마다 꽂힌 책의 권수가 모두 서로 달라야 한다. 둘째, 비어 있는 책장이 있어서는 안 되므로 책장마다 적어도 한 권은 꽂아야 한다. 또한 기증받은 N권은 한 권도 남기지 않고 모두 꽂아야 한다.
사서는 책장끼리 너무 치우치지 않게 꽂고 싶다. 그래서 책이 가장 많이 꽂힌 책장의 권수와 가장 적게 꽂힌 책장의 권수의 차이를 최소로 만들려고 한다. 규칙을 지키며 꽂는 방법이 아예 없을 수도 있는데, 그런 경우에는 -1을 답으로 한다.
책의 수 N과 책장의 수 K가 주어졌을 때, 가장 많이 꽂힌 책장과 가장 적게 꽂힌 책장의 권수 차이의 최솟값을 구하는 프로그램을 작성하여라.
예를 들어 N=10권을 K=3개의 책장에 꽂는 경우를 보자. 권수가 서로 다르고 빈 책장이 없도록 10을 세 수로 나누는 방법은 다음의 표와 같이 네 가지다.
| 나누는 방법 | 가장 많은 책장 | 가장 적은 책장 | 차이 |
|---|---|---|---|
| 1, 2, 7 | 7 | 1 | 6 |
| 1, 3, 6 | 6 | 1 | 5 |
| 1, 4, 5 | 5 | 1 | 4 |
| 2, 3, 5 | 5 | 2 | 3 |
차이가 가장 작은 것은 2, 3, 5로 나누는 방법이고 그 차이는 3이다. 따라서 현재 예시에서 정답은 3이다.
반면에 N=5권을 K=3개의 책장에 꽂으려면, 권수가 서로 다르고 모두 한 권 이상이어야 하므로 적어도 1과 2와 3을 더한 6권이 있어야 한다. 책이 5권뿐이라 꽂는 방법이 없으므로 이 경우의 답은 -1이다.
K가 1인 경우도 있다. 책장이 하나뿐이면 그 책장에 N권을 모두 꽂게 되고, 가장 많은 책장과 가장 적은 책장이 같으므로 차이는 0이다.
입출력 예시
예시 1
입력
10 3
출력
3
예시 2
입력
6 3
출력
2
예시 3
입력
5 3
출력
-1
예시 4
입력
1 1
출력
0
입력 조건
가장 먼저 책의 수 N과 책장의 수 K가 첫째 줄에 공백 하나로 구분되어 차례대로 주어진다. N은 1 이상 1,000,000 이하의 자연수이고, K는 1 이상 1,000 이하의 자연수다.
입력은 이 한 줄이 전부다. N이 K보다 작은 경우도 주어지며, 그런 경우에는 책장마다 한 권씩 꽂을 수도 없으므로 규칙을 지키며 꽂는 방법이 없다.
출력 조건
가장 많이 꽂힌 책장과 가장 적게 꽂힌 책장의 권수 차이의 최솟값을 첫째 줄에 출력한다. 규칙을 지키며 꽂는 방법이 없으면 -1을 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 책장마다 꽂힌 권수가 모두 서로 달라야 하고, 비어 있는 책장이 있어서는 안 됩니다
- 기증받은 N권을 한 권도 남기지 않고 모두 꽂아야 합니다
- 규칙을 지키며 꽂는 방법이 없으면 -1을 출력합니다
- 읽어야 하는 수는 첫째 줄의 N과 K 두 개입니다
- 출력은 수 하나와 줄바꿈뿐입니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 15개이고, 그 가운데 4개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 4개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
10 3
3
6 3
2
5 3
-1
1 1
0
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 4개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.