개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다.
우리는 게임을 준비하기 위해서, 개의 공을 개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, 개의 공을 개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.
게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다.
공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다.
1. 개의 공을 개의 바구니에 빠짐없이 나누어 담는다.
2. 각 바구니에는 1개 이상의 공이 들어 있어야 한다.
3. 각 바구니에 담긴 공의 개수는 모두 달라야 한다.
4. 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.
첫 번째 줄에 공의 개수를 나타내는 과 팀의 수를 나타내는 정수 가 주어진다.
개의 공을 개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 출력한다.
공이 담긴 개수가 다르면서 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.
1. 바구니에 순차적으로 1,2,3,4...n-1,n개를 담는다.
2. 만약 이 과정에서 바구니에 나눠 담을 수 없다면 -1을 출력한다.
3. 순차적으로 분배한 다음에도 공이 남아있을 때,
아래 예시를 보면 쉽게 이해할 수 있다.
공의 개수 바구니1 바구니2 바구니3 차이
6 1 2 3 2
7 1 2 4 3
8 1 3 4 3
9 2 3 4 2
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class BJ_19939 {
public static void main(String[] args) throws IOException {
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 N = Integer.parseInt(st.nextToken());
// 바구니 수
final int K = Integer.parseInt(st.nextToken());
for (int i = 1; i < K + 1; i++) {
N -= i;
if (N < 0) {
break;
}
}
if (N >= 0) {
if (N % K > 0) {
sb.append(K);
} else {
sb.append(K-1);
}
} else {
sb.append(-1);
}
sb.append("\n");
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
}
참고 블로그
https://velog.io/@phjppo0918