[백준] 알고리즘 분류(그리디 알고리즘,JAVA)19939번, 박 터뜨리기

문제 링크

19939번: 박 터뜨리기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 바구니에는 공을 모두 다른 숫자로 담아야 합니다.

2. 바구니에는 최소 1개에 공이 담겨져있어야 합니다.

3. 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소값을 결과로 출력합니다.

4. 나눠담을 수 없으면 -1을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 바구니에 담을 수 있는 최소의 경우를 공을 담은 후, 나머지 공을 넣습니다.

 

3. 조건에 맞게 담을 수 없으면 -1, 조건에 맞게 담으면 공의 개수 차이를 결과로 출력합니다.

 

 

바구니에 담는 최소 경우.

 

각 바구니에 등차수열 +1 형식으로 공을 담으면 모든 공의 개수가 다른 최소의 경우로 담을 수 있습니다.

 

K = 5

 

최소의 경우

 

바구니1	바구니2	바구니3	바구니4	바구니5
1	2	3	4	5

 

모든 바구니의 1개 이상 담으며, 담은 공의 개수가 다르려면 위와 같은 형태가 최소한 되어야 합니다.

 

남은 공이 있을 때

 

공이 많이 담긴 바구니부터 1개씩 추가해줍니다.

 

최소 경우의 공을 담은 후 남은 공이 3개일 때

 

바구니1	바구니2	바구니3	바구니4	바구니5
1	2	4	5	6

가장 큰 바구니 - 작은 바구니 = 6 - 1 = 5

 

최소의 경우 공의 개수(∑) : 1 + .... + (K-1) + K 

 

공의 개수(N) < 최소의 경우 공의 개수(∑)

 

바구니에 담을 수 없어서 -1을 결과로 출력합니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N = 6

K = 3

 

2. 바구니에 담을 수 있는 최소의 경우를 공을 담은 후, 나머지 공을 넣습니다.

조건에 맞게 바구니에 담을 수 있는지 확인!

최소 경우 공의 개수(∑) : 1 + 2 + 3 = 6

공의 개수(6) ≥ 최소 경우 공의 개수(6) 성립!

 

바구니에 최소 경우로 바구니에 담기

 

바구니1	바구니2	바구니3
1	2	3

 

최소 경우를 담은 후 남은 공 확인 : 6 - 6 = 0개

 

최소 경우 존재하지 않으므로 바구니에 공 담기 완료!

 

3. 조건에 맞게 담을 수 없으면 -1, 조건에 맞게 담으면 공의 개수 차이를 결과로 출력합니다.

 

가장 많이 담긴 바구니 : 3가장 적게 담긴 바구니 : 1

 

개수 차이 : 3 - 1 = 2개

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용하여 N과 K를 띄어쓰기 기준 나누었습니다.
• sigma를 사용하여 바구니 담는 최소 경우 공의 개수를 구합니다.
• 최소 경우 공의 개수를 이용하여 조건에 맞게 바구니에 담을 수 있는지 확인합니다.
• 담을 수 있으면 남은 공을 확인하여 각 바구니에 담습니다.
• 담을 수 없으면 -1, 담았으면 최대, 최소 공의 차이를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• sigma함수는 ∑을 구현한 것으로, 최소 경우 공의 개수를 구합니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int min = sigma(K);	//최소 경우 공의 개수 구하기
        if(min > N)		//최소 경우도 바구니에 담지 못할 때
            bw.write("-1");		//조건에 맞게 바구니에 담지 못함!
        else{
            //최소 경우 바구니에 담은 후
            int answer = K-1;
            N -= min;		//남은 공 개수
            if(N%K != 0)	//남은 공을 1개씩 나눠서 담았을 때 모두 같게 나누지 못할 때
                answer++;		//최소와 최대 차이가 1이 더 벌어집니다.
            bw.write(answer + "");	//최대, 최소 공의 차이 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //∑를 구현한 함수
    static int sigma(int n){
        int result = 0;
        for(int i=1;i<=n;i++)
            result += i;
        return result;
    }
}