[ 탐욕 알고리즘 ] 그리디 알고리즘(백준 11047, 1541)

 그리디 알고리즘

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

* 항상 최적의 해를 보장하는 것은 아니기에 그리디 알고리즘이 문제에 적합한지 판단해야한다.

 

💡  그리디 알고리즘의 핵심 이론

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.

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

3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

 

 11047 : 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 A_i가 오름차순으로 주어진다. (1 ≤ A_i ≤ 1,000,000, A₁ = 1, i ≥ 2인 경우에 A_i는 A_i-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

입력	출력
10 4200 1 5 10 50 100 500 1000 5000 10000 50000	6
10 4790 1 5 10 50 100 500 1000 5000 10000 50000	12

 

문제 풀이

• 큰 가치의 동전부터 소모하면서 반복

 

실행 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P11047_Greedy {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //동전 종류의 갯수
        int K = Integer.parseInt(st.nextToken()); //만들어야하는 금액
        int[] A = new int[N]; //동전의 가치를 담을 배열
        for(int i=N-1;i>=0;i--){
            A[i] = Integer.parseInt(br.readLine());
        }

        // 동전을 큰 가치부터 소모
        int num=0;
        for(int i=0;i<N;i++){
            num += K / A[i];
            K %= A[i];
            if(K==0)
                break;
        }

        System.out.println(num);
    }
}

 

 1541 : 잃어버린 괄호

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

출력

첫째 줄에 정답을 출력한다.

입력	출력
55-50+40	-35
10+20+30+40	100
00009-00009	0

 

문제 풀이

• '+'연산에 무조건 괄호치기!

 

실행 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class P1541_Greedy {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String[] A = s.split("-");
        int result = 0;

        // '-'를 기준으로 나눈다
        for(int i=0;i<A.length;i++){
            if(i==0){ //첫번째나오는 숫자는 무조건 더해줌
                result += SumFun(A[i]);
            }else{ //이 외에 수식이나 숫자는 계산해서 빼줌
                result -= SumFun(A[i]);
            }
        }
        System.out.println(result);
    }

    // 문자열을 +기준으로 나누고 다 더해서 반환한다.
    private static int SumFun(String s) {
        String[] nums = s.split("\\+");
        int sum = 0;
        for (String num : nums)
            sum += Integer.parseInt(num);
        return sum;
    }
}