[백준, Java] 19590번, 비드맨, (그리디)

문제 링크

19590번: 비드맨

 

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 서로 다른 종류의 구슬이 부딪히면 서로 깨져서 없어진다.

2. 구슬을 최소한으로 만들려고 한다.

3. 구슬의 종류는 N개이며, 각각 개수가 존재합니다.

4. 구슬을 최대한 깨뜨렸을 때, 남은 구슬의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 구슬을 깨드리는 과정에 대한 경우에 대해서 탐색합니다.

 

3. 탐색을 통해 얻은 남은 구슬의 개수를 결과로 출력합니다.

 

 

 

구슬 깨드리기(그리드)

 

구슬의 개수가 가장 많이 깨뜨렸다는 것은 마지막에 남은 구슬의 종류가 1개만 남아있어야 합니다.

 

→ 2개 이상 남아있다면 아직 깨드릴 수 있는 경우가 존재하기 때문입니다.

 

즉, 구슬의 종류가 1개가 남아야하며, 최대한 구슬을 깨뜨리기 위해서는 가장 개수가 많은 종류의 구슬과 가장 적은 개수인 종류의 구슬을 부딪히면 되면 가장 많은 구슬을 깨뜨리게 됩니다.

 

구슬을 최대한 깨드릴 때 2가지 경우로 나눌 수 있습니다.

 

 

1. 가장 개수가 많은 구슬 ≥ 남은 구슬의 개수

 

가장 개수가 많은 구슬로 나머지 다른 구슬을 깨뜨릴 수 있다고 해석할 수 있습니다.

 

즉, 모든 구슬을 최대한 깨뜨리는 것은 {가장 개수가 많은 구슬 - 남은 구슬의 개수}으로 구할 수 있습니다.

 

[점화식]

 

가장 개수가 많은 구슬 - 남은 구슬의 개수 = 구슬 최소 값

 

 

2. 가장 개수가 많은 구슬 < 남은 구슬의 개수

 

가장 개수가 많은 구슬로 나머지 다른 구슬을 깨뜨릴 수 없습니다.

 

가장 개수가 많은 종류의 구슬과 가장 적은 개수인 종류의 구슬을 부딪히면 되면 가장 많은 구슬을 깨뜨리는 과정을 반복하게 됩니다.

 

(5, 4, 2)의 구슬들이 존재한다면

 

(5, 4, 2) → (4, 4, 1) → (4, 3, 0) → (3, 2, 0) → (2, 1, 0) → (1, 0, 0)

 

최대 개수를 가진 구슬이 2번째 개수를 가진 구슬과 개수가 항상 동일해지게 됩니다.

 

마지막에는 그 2가지의 구슬만 남게되어 서로 1개씩 구슬이 깨뜨리는 과정을 진행하게 됩니다.

 

즉, 모든 구슬의 개수에 대해서 2개식 구슬이 깨지면서 모두 깨지거나 1개가 남게 됩니다.

 

[점화식]

 

전체 구슬의 개수가 짝수일 때

 

→ 2개씩 모두 깨지기 때문에 마지막에는 구슬은 남아있지 않게 되어 0이 됩니다.

 

 

전체 구슬의 개수가 홀수일 때

 

→ 2개씩 깨지고 마지막 남은 구슬 1개는 깨지지 못하기 때문에 1이 됩니다.

 

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 3.

 

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

 

N : 3

 

 

2

2

4

 

 

2. 구슬을 깨드리는 과정에 대한 경우에 대해서 탐색합니다.

 

구슬의 총 개수 : 8

 

개수가 가장 큰 구슬의 값 : 4

 

 

1. 가장 개수가 많은 구슬 ≥ 남은 구슬의 개수

 

 

4 ≥ 8 으로써 조건에 만족하지 않습니다.

 

 

 

 

2. 가장 개수가 많은 구슬 < 남은 구슬의 개수

 

4 ＜ 8 으로써 조건에 만족합니다.

 

[점화식]

 

전체 구슬의 개수(8)가 짝수일 때

 

→ 2개씩 모두 깨지기 때문에 마지막에는 구슬은 남아있지 않게 되어 0이 됩니다.

 

 

3. 탐색을 통해 얻은 남은 구슬의 개수를 결과로 출력합니다.

 

점화식을 통해 얻은 값 : 0

 

0 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 구슬에 대해서 전체 개수와 최대 구슬의 개수를 구합니다.
• "가장 개수가 많은 구슬 ≥ 남은 구슬의 개수"과 "가장 개수가 많은 구슬 < 남은 구슬의 개수"에 대해서 조건을 구분합니다.
• 조건에 맞는 점화식을 통한 결과를 BufferdWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

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

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));
        int N = Integer.parseInt(br.readLine());
        //개수 최대인 구슬
        int max = 0;
        //모든 구슬 개수의 합
        long sum = 0;
        //입력되는 구슬의 정보 저장 및 합과 최대 개수 구하기
        for(int i=0;i<N;i++){
            int num = Integer.parseInt(br.readLine());
            sum += num;
            max = Math.max(max, num);
        }
        //1. 가장 개수가 많은 구슬 ≥ 남은 구슬의 개수
        if( max >= (sum - max)){
            bw.write(String.valueOf(max - (sum - max)));
        }else{	//2. 가장 개수가 많은 구슬 < 남은 구슬의 개수
            bw.write(String.valueOf(sum % 2));
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}