문제
K개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다.
우리는 게임을 준비하기 위해서, N개의 공을 K개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, N개의 공을 K개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.
게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다.
공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다.
N개의 공을 K개의 바구니에 빠짐없이 나누어 담는다.
각 바구니에는 1개 이상의 공이 들어 있어야 한다.
각 바구니에 담긴 공의 개수는 모두 달라야 한다.
가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.
위의 규칙을 모두 만족하며 N개의 공을 K개의 바구니에 나눠 담을 때, 나눠 담을 수 있는지 여부를 결정하고, 담을 수 있는 경우에는 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 계산해서 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 공의 개수를 나타내는 N과 팀의 수를 나타내는 정수 K가 주어진다
출력
N개의 공을 K개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 출력한다.
제한
2 <= N <= 100,000
2 <= K <= 1,000
풀이
처음에 바구니에 순차적으로 1,2,3,4, .... ,n-1, n 개의 공을 넣는다.
만약 이 과정에서 공의 개수가 부족하다면, 그 경우에는 나눠서 담을 수 없는 경우이다.
순차적으로 분배한 다음에도 공이 남아있을 때, 만약 공의 개수를 바구니의 개수로 나눴을 때의 나머지가 0 초과라면 바구니 개수를 출력, 0이라면 바구니 개수 -1을 출력한다.
예를 들어, 공은 10개, 바구니는 3개이다. 각 바구니에 1, 2, 3개의 공을 넣는다. 그럼 남은 공의 개수는 4개.
그럼 각 바구니에 1개 씩 분배 후 남은 한 개를 제일 개수가 많은 바구니에 넣는다(그래야 공의 개수가 일치하는 수가 없으니까, 만약 공이 11개여서 맨 마지막에 공이 2개가 남는다면, 두번째 세번째 바구니에 각각 하나씩 넣으면 된다.)
그렇게 되면 각 바구니는 2, 3, 5개의 공을 가지고 있고, 5 - 2는 3, 바구니의 개수와 같다.
만약 공이 9개라면, 처음에 1, 2, 3개 분배, 각 바구니에 1개 씩 분배하면 2, 3, 4 개, 4 - 2 = 2 이므로 바구니 개수 - 1 과 같다.
소스코드
import java.util.*;
import java.io.*;
public class Main{
public static void main(String [] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int ball = Integer.parseInt(st.nextToken());
final int basket = Integer.parseInt(st.nextToken());
for(int i=1;i<basket+1;i++) {
ball-=i;
if(ball < 0) {
break;
}
}
if(ball >=0) {
if(ball%basket > 0) {
sb.append(basket);
}else {
sb.append(basket-1);
}
}else {
sb.append(-1);
}
sb.append("\n");
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
}