[백준 19939번] 박 터뜨리기 - java(자바) 그리디 알고리즘

7월 12일, 제가 공군 입대한 다음 날이네요ㅎㅎ

폰이나 블로그를 할수 없으므로 이 포스트 부턴 미리 작성한 글을 예약 발행한 것입니다.

오늘 부터 매주 화목에 발행 예약 해놨으므로 매주 화목에 보러오세요!

---

박 터뜨리기

문제

 K개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다.

우리는 게임을 준비하기 위해서, N개의 공을 K개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, N개의 공을 K개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.

게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다.

공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다.

1.  N개의 공을 K개의 바구니에 빠짐없이 나누어 담는다.
2. 각 바구니에는 1개 이상의 공이 들어 있어야 한다.
3. 각 바구니에 담긴 공의 개수는 모두 달라야 한다.
4. 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.

위의 규칙을 모두 만족하며 N개의 공을 K개의 바구니에 나눠 담을 때, 나눠 담을 수 있는지 여부를 결정하고, 담을 수 있는 경우에는 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 계산해서 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 공의 개수를 나타내는 N과 팀의 수를 나타내는 정수 K가 주어진다.

출력

 N개의 공을 K개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 출력한다.

---

예제 입력 1

5 3

예제 출력 1

-1

---

예제 입력 2

6 3

예제 출력 2

2

---

java 코드

박터트리기는 그리디 알고리즘으로, 선택의 순간마다 최적의 상황을 구성해서 최적의 답을 가장 효율적으로 구하면 됩니다.

최적의 상황을 생각하는것도 수학적으로 생각하고, 최적의 답을 도출해내는것도 수학적으로 효율적으로 만들어야합니다.

위에 조건들을 잘생각해보면 모든 바구니에 똑같이 공을 미리 넣어주고 시작하는것이 최적의 상황이겠죠?

 

그리디 알고리즘에 대한 설명은 밑에 있습니다.

 

모든 k개의 바구니가 일단 똑같이 공을 넣어줘야하는데, 그것을 base라고 하겠습니다.

base를 다 넣어준 후 남은 공들을 배치해서 모든 바구니가 다 다른 공을 가지고 있도록 해야하는데, 그러려면 최소한 꼭 1+2+3...+k개의 공이 추가적으로 있어야하므로 base는 총 공의 갯수에 필수 공들을 빼고 바구니 갯수로 나눠줍니다.

 

연습장에다가 바구니에다가 추가공들을 넣어주는것을 그리면서 계속 고민하면, 정확히  1+2+3...+k의 공이 남아서 배치하면 1,K의 차이므로 k-1이 답으로 나오고,

1개가 더 과잉되든 2개든 k만큼만 차이나는것을 그려서 알 수 있습니다.

수학적으로 공식화 시켜서 최대한 효율적으로 구할수 있도록 해야합니다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args)   {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); // number of balls
        int k = scan.nextInt(); // number of baskets
        scan.close();
        int[] baskets = new int[k];
        // if k baskets, add base to all baskets
        // after, need AT LEAST additional (1+2+3+....+k) balls
        int base = (n-((k*(k+1))/2));
        if (base<0) {
            System.out.println("-1");
            return;
        }
        for (int i = 0; i < baskets.length; i++) {
            baskets[i] = (base / k);
            n -= (base / k);
        }
        if (n==((k*(k+1))/2)) {
            System.out.println(k-1);
        }
        else{
            System.out.println(k);
        }
    }
}

---

그리디 알고리즘

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻입니다.
탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법입니다.
여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없지만, 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들입니다.

---

그리디 알고리즘의 조건

그리디 알고리즘 문제의 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것으로,  문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것입니다.