(Baekjoon) GreedyAlgorithm - (17) 저울

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

2437번: 저울

 

 

 

 

= weight[] = 3 1 6 2 7 30 1

1) 우선 오름차순으로 정렬을한다. 

= 1 1 2 3 6 7 30

2) 숫자 1이 들어있지않다면 답은 1 아니라면 연속성을 살펴본다.

예를들어서 1 1 2 3 4 4 , n과 n+1 관계에서 (n+1 - n) <= 1 라고 한다면 연속성이 성립한다고 볼수있다.

ex) 1123 , 23444 , 1111223, 1234567 

3) 연속성이 성립되지 않는곳까지 탐색한다.

= 1 1 2 3 까지 연속성이 성립 6부터 성립안함

4) 1 1 2 3 까지를 전부더한다. 이것을 sum에다가 넣는다. 그리고 값 3의 index를 pivot으로 정한다. 

= pivot = 3, sum = 7

5) pivot = 3 + 1 부터 검사를 시작한다.

 

pivot = 4 -> weight[4] = 6 이다. 해당값이 sum+1보다 크다면 그값은 

연속적이지 않다. 그러므로 만들수없는 수가 생긴다.

6은 sum+1 = 8보다 작으므로 조건이 성립한다. 해당값과 sum을 더해서 sum에다가 넣는다.

(sum = 13)

 

pivot = 5 -> weight[5] = 7 이다. 해당값이 sum+1보다 크다면 그값은

연속적이지 않다. 그러므로 만들수없는 수가 생긴다.

7은 sum+1 = 14보다 작으므로 조건이 성립한다. 해당값과 sum을 더해서 sum에다가 넣는다.

(sum = 20)

 

pivot = 6 -> weight[6] = 30 이다. 해당값이 sum+1보다 크다면 그값은

연속적이지 않다. 그러므로 만들수없는 수가 생긴다.

30은 sum+1 = 20보다 크므로 조건이 성립하지 않는다. 그러므로 20 이상인 수는 만들수없다.

 

그러므로 답은 21이다.

 

이해가 가지 않는다면

1 1 2 3 6 7 30 을

1 1 2 3 9 10 20 으로 해보고 따져보고

1 1 2 3 6  7 20 으로 해보고 따져보자.

그러면 왜 내가 위와같이 풀었는지 알수있다.

 

다른사람들보다 코드가 난잡한데 결론적으로 다른사람들도 이와 비슷하게 풀었다.

 

package GreedyAlgorithm;

import java.util.Arrays;
import java.util.Scanner;

public class _2437 {
    static int weight[];
    static int pivot, sum;

    static void ck_continuity() {

        for (int i = 1; i < weight.length; i++) {
            if (weight[i] - weight[i - 1] <= 1)
                pivot = i;
            else
                break;
        }
    }

    static void find_min() {
        for (int i = pivot+1; i < weight.length; i++) {
            if (weight[i] > (sum + 1)){
                break;
            }
            else
                sum += weight[i];
        }

    }

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        weight = new int[N];
        for (int i = 0; i < N; i++) {
            weight[i] = sc.nextInt();
        }
        Arrays.sort(weight);


        if (Arrays.binarySearch(weight, 1) < 0) // 이진탐색으로 1이 없다면 1출력
            System.out.println("1");
        else if(N==1){
            if(weight[0] != 1)
                System.out.println("1");
            else   
                System.out.println("2");
        }
        else{

            ck_continuity(); // 연속성검사
            
            for (int i = 0; i <= pivot; i++) {
                sum += weight[i];
            }
            // for (int i = 0; i < weight.length; i++) {
            //     System.out.print(weight[i]+" ");
            // }
            // System.out.println();
            // System.out.println("pivot : " + pivot + " sum : "+ sum );
            if(pivot == weight.length-1)
                System.out.println(sum+1);
            else{
                find_min();
                System.out.println(sum+1);
            }

        }

        sc.close();

    }
}

 

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study