[BOJ] 24단계 그리디 알고리즘

1

11047

동전 0

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        int N = Integer.parseInt(split[0]);
        int K = Integer.parseInt(split[1]);
        int[] value = new int[N];
        for(int i = N - 1; i >= 0; i--) {
            value[i] = Integer.parseInt(reader.readLine());
        }

        int cnt = 0;
        for(int i = 0; i < N; i++) {
            if(K >= value[i]) {
                cnt += K / value[i];
                K = K % value[i];
            }
            if(K == 0) {
                break;
            }
        }
        System.out.println(cnt);
    }
}

 

2

1931

회의실 배정

 

3

11399

ATM

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[] time = new int[N];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            time[i] = Integer.parseInt(tokenizer.nextToken());
        }
        Arrays.sort(time);
        int prev = 0;
        int result = 0;
        for(int i = 0; i < N; i++) {
            prev += time[i];
            result += prev;
        }
        System.out.println(result);
    }
}

*prev(이전 누적 값)의 값을 작게 만들수록 최종 합이 최소가 된다.

*시간을 오름차 순으로 정렬 후 누

 

4

1541

잃어버린 괄호

괄호를 적절히 쳐서 식의 값을 최소로 만들기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine(), "+-", true);
        List<Integer> operand = new ArrayList<>();
        while(tokenizer.hasMoreTokens()) {
            String token = tokenizer.nextToken();
            if(token.equals("+")) {
                int op1 = operand.remove(operand.size() - 1);
                int op2 = Integer.parseInt(tokenizer.nextToken());
                operand.add(op1 + op2);
            } else if(!token.equals("-")) {
                operand.add(Integer.parseInt(token));
            }
        }
        int result = operand.get(0);
        for(int i = 1; i < operand.size(); i++) {
            result -= operand.get(i);
        }
        System.out.println(result);
    }
}

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer subExp = new StringTokenizer(reader.readLine(), "-");
        int result = Integer.MAX_VALUE;
        while(subExp.hasMoreTokens()) {
            StringTokenizer addExp = new StringTokenizer(subExp.nextToken(), "+");
            int temp = 0;
            while(addExp.hasMoreTokens()) {
                temp += Integer.parseInt(addExp.nextToken());
            }
            if(result == Integer.MAX_VALUE) {
                result = temp;
            } else {
                result -= temp;
            }
        }
        System.out.println(result);
    }
}

• + +, + - 는 결과가 순서의 영향을 받지 않는다.
• - + : - (+) 가 최소가 됨
• - - : (-) - 가 최소가 됨

=> + 연산을 먼저, - 연산은 앞에서부터 순서대로

 

 

5

13305

주유소

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int[] distance = new int[N-1];
        for(int i = 0; i < N - 1; i++) {
            distance[i] = Integer.parseInt(tokenizer.nextToken());
        }
        tokenizer = new StringTokenizer(reader.readLine());
        long min = Integer.MAX_VALUE;
        long totalPrice = 0;
        for(int i = 0; i < N - 1; i++) {
            int price = Integer.parseInt(tokenizer.nextToken());
            if(price < min) {
                min = price;
            }
            totalPrice += min * distance[i];
        }
        System.out.println(totalPrice);
    }
}