문제 이해

4가지 조건을 모두 충족시키면서 공을 바구니에 나눠 담을려고 한다.
1. N개의 공을 K개의 바구니에 빠짐없이 나누어 담는다.

• 바구니 개수 : K개, 담아야 하는 공 개수 : N개

2. 각 바구니에는 1개 이상의 공이 들어 있어야 한다
3. 각 바구니에 담긴 공의 개수는 모두 달라야 한다
4. (가장 많이 담긴 공 개수) - (가장 적게 담긴 공 개수) 값이 최소가 되어야 한다

이 경우, (가장 많이 담긴 공 개수) - (가장 적게 담긴 공 개수)를 출력하세요

문제 풀이

알고리즘적으로도 풀 수 있지만, 수학적으로 접근하는 것이 조금 더 쉬운 문제였다.

먼저, 1번 조건은 간단히 해결할 수 있는 문제이다.
그냥 담는 공의 개수가 전부 합해서 N이 되면 된다.

2번 조건은 간단한 수학적 기믹으로 해결할 수 있다.
그냥 최초에 모든 바구니에 1개씩 공을 넣고 시작하는 것이다. 그렇다면 모든 바구니에는 무조건 1개 이상의 공이 들어 있을 것이다.
따라서, N = N - M으로 생각했다.

3번, 4번 조건을 동시에 만족시키기가 이 문제의 핵심이라고 볼 수 있다.
그런데, 이 조건을 해결하면서 3,4번 조건까지 모두 충족시키는 법을 발견했다.
바로, (1,2,...,M)개씩 바구니에 공을 넣고, 이후 M번째 바구니부터 공을 한개씩 넣고, (M-1)번째 바구니에 공을 넣는 방식을 계속해서 수행하면 될 것이라고 생각했다.

이 경우, 공의 개수 차이는 M-1이거나 M이 될 것이다.

• M-1인 경우 : 마지막에 넣은 공이 첫번째 바구니였을 Case
• M인 경우 : 이외의 Case

즉, (M-1)인 경우는 $\frac{M*(M+1)}{2} + M* T$

따라서, N - (M*(M+1))/2를 수행하고, 이 값이 M으로 나눠지면 답은 M-1, 아닐 경우 M, 만약 음수라면 2,3 조건을 충족시키지 못하는 Case이므로 -1을 출력했다.

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		FastReader sc = new FastReader();

		int N = sc.nextInt(); // 공
		int M = sc.nextInt(); // 바구니
		
		int minus = (M * (M+1))/2;
		
		N = N - minus;
		
		if(N<0) {
			System.out.println(-1);
			return;
		}
		
		
		if(N%M==0) {
			System.out.println(M-1);
		}
		else {
			System.out.println(M);
		}
		
	}	

	static class FastReader // 빠른 입력을 위한 클래스
}

결과

• 2번째 줄 틀렸습니다 : (M-1)이 출력 될 수 있다는 가능성을 고려하지 못했다.