[백준/BOJ]19939. 박 터뜨리기 [Silver 5]

19939. 박 터뜨리기

문제출처 : https://www.acmicpc.net/problem/19939

처음 이 문제를 보고 진짜 쉬울것 같았는데, 알고리즘 자체는 쉬운데 조건찾는데 좀 애를먹었다.

code

#include <stdio.h>
int main()
{
	int N, K;
	scanf("%d %d", &N, &K);
	if ((K*(K+1)/2 > N))
		printf("-1");
	else
	{
		if (K % 2 != 0)
		{
			if (N % K == 0)
				printf("%d", K - 1);
			else
				printf("%d", K);
		}
		else
		{
			if (N % K == K / 2)
				printf("%d", K - 1);
			else
				printf("%d", K);
		}
	}
}

(K*(K+1)/2 > N)은 N개의 공을 K개의 바구니에 서로 다른갯수로 나눌수 없을때 -1을 반환 하도록 했다.
예를들어 N==5 K==3이면 3개의 바구니에 공을 나눌 수 있는 경우는 1,2,3이렇게 밖에 없는데 이러면 공이 6개가 되므로 나눌수 없는 케이스다.
그러므로 1부터 K까지의 합(서로다른 공의 갯수로 바구니에 넣는경우)은 공의 개수N보다 커야한다.
그리고 K가 홀수일때랑 짝수일때 이렇게 2개의 경우의 수를 두고 구별했다.

또, 공의 개수 차이는 최소가 되어야 하므로 K개를 넘지 않을 것이다.

(1,2,3 / 99 100 101 / 999 1000 1001 / 1998 1999 2001 2002 등등 )

그리고 조건에 따라 K개가 될수도 K-1개가 될수도 있었는데, 나도 이 조건을 찾는데 좀 애를 먹었는데, 결국 노가다를 시전했다.

결과는 다음과 같다.

K홀수
11 3
2 4 5-------------3(K)
12 3
3 4 5----------2(K-1)
13 3
346 --------3(K)
14 3
356 -------3(K)
15 3
456-----------2(K-1)
16 3
457-----------3(K)
17 3
467 -------------3(K)
18 3
5 6 7-------------2(K-1)
19 3
5 6 8-----------3(K)
20 3
578-------------3(K)
21 3
6 7 8 ----------2(K-1)
22 3
679 ------------3(K)

결론 : K-1일떄는
N이 K의 약수이다

K짝수
10 4
1 2 3 4---------------3(K-1)
11 4
1 2 3 5----------------4(K)
12 4
1245 ------------4(K)
13 4
1345 --------4(K)
14 4
2 3 4 5 --------3(K-1)
15 4
2346 -------4(K)
16 4
2356 -----------4(K)
17 4
2456--------------4(K)
18 4
3 4 5 6----------3(K-1)
19 4
3 4 5 7-----------4(K)
20 4
3467 -------4(K)
21 4
3567 -----------4(K)
22 4
4 5 6 7----------3(K-1)
결론 : K-1일때는
N%K == K/2이다

그러므로 K-1일때 조건에 부합하면 K-1을 출력한다.