[백준 11047번, 1541번] 그리디 알고리즘(Java)

그리디 알고리즘

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

 

032. 동전 개수의 최솟값 구하기(백준 11047번)

 

이 문제는 그리디 알고리즘으로 풀 수 있도록 뒤에 동전 가격 A가 앞에 나오는 동전 A_i-1의 배수가 된다는 조건을 부여했다.

즉, 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        
        int count = 0;
        for(int i=n-1; i>=0; i--) {
            if(arr[i] <= k) {
                count += (k/arr[i]);
                k = k % arr[i];
            }
        }
        System.out.println(count);
    }
}

 

 

 

036. 최솟값을 만드는 괄호 배치 찾기(백준 1541번)

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String expression = sc.nextLine(); // "55-50+4"
        
        String[] strArr = expression.split("-"); // ["55", "50+4"]
        int answer = 0;
        for(int i=0; i<strArr.length; i++) {
            int temp = mySum(strArr[i]);
            if(i == 0) answer += temp;
            else answer -= temp;
        }
        System.out.println(answer);
    }
    
    private static int mySum(String str) {
        int sum = 0;
        String[] temp = str.split("[+]"); // ["50", "4"]
        for(int i=0; i<temp.length; i++) {
            sum += Integer.parseInt(temp[i]);
        }
        return sum;
    }
}