[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2437번, 저울

문제 링크

2437번: 저울

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 주어진 추를 이용하여 측정할 수 있는 무게의 최소값을 결과로 출력합니다.

2. N개의 무게가 양수인 추가 주어집니다.

 

알고리즘 진행 순서.

 

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

 

2. 추의 무게를 오름차순 정렬한 뒤, 추의 무게를 더해서 측정할 수 있는 최소값을 탐색합니다.

 

3. 측정할 수 있는 최소값을 결과로 출력합니다. 

 

 

측정할 수 있는 무게 확인하기.

 

예를 들어 

추의 무게가 아래와 같을 때

1

1

3

4

7

 

[ 1 ]로 만들 수 있는 측정 무게 최대값 :1

{1}

[ 1 , 1]로 만들 수 있는 측정 무게 최대값 : 2

{1}, {1 + 1}

[ 1, 1, 3 ]로 만들 수 있는 측정 무게 최대값 : 5

{1}, {1 + 1}, {3}, {1 + 3}, {1 + 1 + 3}

[ 1, 1, 3, 4 ]로 만들 수 있는 측정 무게 최대값 : 9

{1}, {1 + 1}, {3}, {4}, {1 + 4}, {1 + 1 + 4}, {3 + 4}, {1 + 3 + 4}, {1 + 1 + 3 + 4}

[ 1, 1, 3, 4, 7 ]로 만들 수 있는 측정 무게 최대값 : 16

{1}, {1 + 1}, {3}, {4}, {1 + 4}, {1 + 1 + 4}, {7}, {1 + 7}, {1 + 1 + 7}

{3 + 7}, {4 + 7}, {1 + 4 + 7}, {1 + 1 + 4 + 7}, {3 + 4 + 7}, {1 + 3 + 4 + 7}, {1 + 1 + 3 + 4 + 7}

 

다음 값 ≤ 누적합 + 1을 만족하면

무게의 전체합 이하의 무게들은 측정할 수 있습니다.

 

예제입력 3.

 

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

 

N : 7

 

추의 무게

3

1

6

2

7

30

1

 

2. 추의 무게를 오름차순 정렬한 뒤, 추의 무게를 더해서 측정할 수 있는 최소값을 탐색합니다.

 

오름차순 정렬!

1

1

2

3

6

7

30

초기 합 : 0

추의 무게 더하기.

 

1	1	2	3	6	7	30
1

1 ≤ 0 + 1을 만족

합: 1(1이하의 무게 측정 가능)

 

1	1	2	3	6	7	30
1	2

2 ≤ 1 + 1을 만족

합 : 2(2이하의 무게 측정 가능)

 

1	1	2	3	6	7	30
1	2	4

2 ≤ 2 + 1을 만족

합 : 4(4이하의 무게 측정 가능)

 

1	1	2	3	6	7	30
1	2	4	7

3 ≤ 4 + 1을 만족

합 : 7(7이하의 무게 측정 가능)

 

1	1	2	3	6	7	30
1	2	4	7	13

6 ≤ 7 + 1을 만족

합 : 13(13이하의 무게 측정 가능)

 

1	1	2	3	6	7	30
1	2	4	7	13	20

7 ≤ 13 + 1을 만족

합 : 20(20이하의 무게 측정 가능)

 

다음 값 30

30 ≤ 20 + 1을 만족 X

 

3. 측정할 수 있는 최소값을 결과로 출력합니다. 

 

무게를 측정할 수 있는 최대값 : 20

무게를 측정할 수 없는 최소값 : 21

21을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 사용하여 추의 무게 정보를 띄어쓰기 기준 나누었습니다.
• Arrays.sort로 추의 무게를 오름차순 정렬을 하였습니다.
• 무게가 낮은 순으로 누적합을 이용하여 측정할 수 없는 최소값을 구합니다.
• 최소값을 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int N, sum;
    static int[] num;
    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));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        num = new int[N];
        //추의 무게 저장
        for(int i=0;i<N;i++)
            num[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(num);	//오름차순 정렬
        //추의 무게가 1개일 때
        if(N==1){
            if(num[0] > 1)
                bw.write("1");
            else
                bw.write("2");
        }else{	//추의 무개가 여러개 일 때
            sum = 0;
            //무게가 작은 순부터 탐색.
            for(int i=0;i<N;i++){
                if(sum+1 < num[i])	//다음 값 ≤ 누적합+1 만족 안할 때
                    break;
                else	//다음 값 ≤ 누적합+1 만족할 때
                    sum += num[i];
            }
            bw.write((sum+1) + "");	//측정할 수 없는 최소값 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}