[그리디 알고리즘] 백준 11047, 백준 1541

그리디 알고리즘이란 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

 

수행 과정

1. 해 선택 : 최선의 선택지를 해로 선택한다.

2. 적절성 검사 : 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.

3. 1~2 반복

 

 

백준 11047에서 그리디를 적용하기 위해 살펴보면, 최대한 큰 금액의 동전으로 구성하는 것이 최선의 선택지임을 알 수 있다.

public class 동전개수의_최솟값_구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int a[] = new int[n];
        for (int i = 0; i <n; i++) {
            a[i] = sc.nextInt();
        }

        //그리디 알고리즘 -> 최대한 큰 동전을 먼저 사용하기
        int count = 0;
        for(int i = n-1; i>=0; i--) {
            if(a[i] <= k) {
                count += (k/a[i]); // 사용한 동전 수
                k = k%a[i];
            }
        }
        System.out.println(count);
    }
}

 

 

백준 1541 에서 요구하는, 어떻게 하면 최솟값을 만들 수 있을까? -> 빼는 숫자가 크면 클수록 전체 수식의 결과는 최소가 된다. 

 

public class 최솟값을_만드는_괄호_배치_찾기 {
    static int answer= 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String example = sc.nextLine();
        String[] str = example.split("-");
        for (int i = 0; i<str.length; i++) {
            int temp = mySum(str[i]);
            if (i == 0) answer = answer + temp;
            else answer = answer - temp;
        }
        System.out.println(answer);
    }

    private static int mySum(String a) {
        int sum = 0;
        String[] temp = a.split("[+]"); //허상 수량자 에러 해결 -> 대괄호 사용 / split이 +를 잘 인식 못 함..
        for (int i = 0; i<temp.length; i++) {
            sum = sum + Integer.parseInt(temp[i]);
        }
        return sum;
    }
}