[그리디] 백준 19939 박 터뜨리기 | 파이썬 풀이

문제 링크

https://www.acmicpc.net/problem/19939

문제 해석

박 터뜨리기를 위해 공 N개가 주어지는데, 이 공들을 K개의 바구니에 1개이상 담으면서 각각의 바구니에 담긴 공의 갯수를 다르게 하면서, 제일 적은 공이 든 바구니와 제일 많은 공이 든 바구니의 갯수 차이가 최소가 되게 만드는 것이 목표인 문제다. 예를들어 8개의 공이 있으면 3개의 바구니에 담을 때 1, 3, 4 이렇게 담는다면 위의 조건을 만족한다. 답을 낼 수 없으면 -1을 출력한다.

문제 풀이

규칙을 찾아보았다.
바구니의 갯수는 3으로 고정일 때, 공이 6개부터 (1,2,3) 들어갈 수 있다.
공이 7개일때는 1,2,4
공이 8개일 때는 1,3,4
공이 9개일 때는 2,3,4
공이 10개일 때는 2,3,5
공이 11개일 때는 2,4,5
...
바구니가 4개일 때도 마찬가지로, 1,2,3,4 부터 시작해서
1,2,3,5
1,2,4,5
1,3,4,5
2,3,4,5
2,3,4,6
2,3,5,6
...
인 규칙이 적용된다. 이를 배열로 생각해본다면, 1~K바구니를 나열한 다음, K번째 바구니부터 1번째 바구니까지 차례대로 1씩 증가시키는 방법이 되겠다.

import sys
N, K = map(int, sys.stdin.readline().split())

# 1~K까지 나열하는 것이 기본이므로 , 그 합을 만족하지 못한다면 -1 출력
# ex) 5 3가 입력이라면 1,2,3을 나열했을 때 최소 6개의 공부터 가능하다는 점을 이용한다.

if N < K*(K+1)/2: # 1~K까지의 합을 구하는 공식
    print(-1)
else:
    # K번째 바구니를 K인덱스에 놓기 위해 K+1까지 초기화하며 그 값을 arr배열에 입력
    arr = [i for i in range(K+1)]
    # N개의 공을 먼저 놓았다고 가정하므로 N에서 놓은 만큼 빼준것을 count에 넣어준다.
    count = int(N - K*(K+1)/2)
    # index를 K로 초기화
    index = K
    # 마지막 인덱스부터 1인덱스까지 차례차례 1씩 더해주는 로직
    while count > 0: # count의 횟수만큼만 반복
        # index가 1씩 감소하다가 0이 되면, 다시 K로 되돌려준다.
        if index == 0:
            index = K
        arr[index] += 1
        index -= 1
        count -= 1
    # 정답 출력
    print(arr[K] - arr[1])