(Baekjoon) GreedyAlgorithm - (18) 수리공 항승

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

1449번: 수리공 항승

 

오름차순으로 정렬후에 시작한다.(이거 안했다가 한번 틀렸다.)

복잡하게 생각할거 없이 왼쪽부터 차례대로 붙힌다고 생각하면 된다.

왼쪽부터 차례대로 붙히면서 테이프가 닿지 않으면 개수를 하나 추가하고

그다음거에서부터 다시 테이프를 붙힌다. 

 

위의 과정처럼 너무 어렵게 생각했었지만 그냥 함정이였다. 이게 왜 그리디 알고리즘인지 모르겠다.

 

package GreedyAlgorithm;

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

public class _1449 {
    static int leak[];
    static int ck;
    static int base;
    static void check_leak(int L){
        ck = L-1;
        base = leak[0] + ck;
        int min=0;
        for (int i = 0; i < leak.length; i++) {
                if(leak[i] > base){
                    base = leak[i] + ck;
                    min++;
                }
        }
        System.out.println(min+1);

    }

    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int L = sc.nextInt();

        leak = new int[N];

        for (int i = 0; i < N; i++) 
            leak[i] = sc.nextInt();
        
            
        Arrays.sort(leak);

        // for (int i = 0; i < leak.length; i++) {
        //     System.out.print(leak[i]+ " ");
        // }

        check_leak(L);

        sc.close();

    }
}

 

 

 

 

 

 

 

 

백준문제풀이Github : 

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

sdk0213/baekjoon-study