[BOJ] Greedy Algorithm / 16단계

1	11047	동전 0
동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제

import java.io.*;
import java.util.StringTokenizer;
public class Main {
	

	public static void main(String[] args) throws IOException{
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer bd = new StringTokenizer(bfr.readLine()); 
		int T = Integer.parseInt(bd.nextToken());
		int money = Integer.parseInt(bd.nextToken());
		
		int array[] = new int[T];
		
		for(int i=0; i<T; i++) { //사용될 돈 단위 입력받음
			array[i] = Integer.parseInt(bfr.readLine());
		}
		int count = 0;
		

			for(int i=array.length-1; i>=0; i--) {
				if(money/array[i] > 0) {
					count += money/array[i];
					money %= array[i];
				}
			}
		
		
		System.out.println(count);
		
	}

}

T, money = map(int, input().split(' '))

array = []

for i in range(T) :
    array.append(int(input()))

array.reverse()

count =0
for i in array:
    if money // i > 0 :
        count += money//i
        money = money % i

print(count)

---

2	1931	회의실 배정
가능한 한 많은 구간을 선택하는 문제

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[][] times = new int[n][2]; // 0 : start 1 : finish
		
		int min = -1;
		for(int i = 0; i < n; i++) {
			times[i][0] = scan.nextInt();
			times[i][1] = scan.nextInt();
		}
		
		Arrays.sort(times, (a,b) -> a[1] == b[1]? a[0] - b[0] : a[1] - b[1]);
		int cnt = 0; 
		for(int i = 0; i < n; i++) {
			if(times[i][0] >= min) {
				min = times[i][1];
				cnt++;
			}
		}
		System.out.println(cnt);

	}
}

---

3	11399	ATM
기다리는 시간의 합을 최소화하는 문제

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

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int array[] = new int[N];
		
		for(int i=0; i<N; i++)
			array[i] = scan.nextInt();
		
		Arrays.sort(array);
		
		int sum=0;
		for(int i=0; i<N; i++) {
			sum += array[i]*(N-i);
		}
		System.out.println(sum);
	}

}

---

4	1541	잃어버린 괄호
식의 값을 가능한 한 작게 만드는 문제

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String a[] = scan.nextLine().split("\\-");
		
		int sum= Integer.MAX_VALUE;
		
		for(int i=0; i < a.length; i++) {
			int temp =0;
			String b[] = a[i].split("\\+");
			
			for(int j=0; j<b.length; j++) {
				temp += Integer.parseInt(b[j]);
			}
			if (sum== Integer.MAX_VALUE) {
				sum = temp;
			}
			else sum -= temp;
		}
		System.out.println(sum);
	}

}

---

5	13305	주유소
최소 비용으로 주유하여 일직선 도로를 달리는 문제

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		//입력값 입력받기
		int T = scan.nextInt();
		long km[] = new long[T];
		long city[] = new long[T];
		for(int i=0; i<T-1; i++){
			km[i] = scan.nextLong();
		}			
		
		for(int i=0; i<T; i++)
			city[i] = scan.nextLong();
		
		long price = 0;
		
		for(int i=0; i<T-1; i++) {
			
			if(city[i] > city[i+1]) { //다음부분이 현재부분보다 저렴한가?
				price += km[i]*city[i];//현재가격으로 최소거리 이동. 다음지역으로
			}
			else {//현재 도시가 다음지역보다 더 저렴하니 다음지역까지 keep
				city[i+1] = city[i];
				price += km[i]*city[i]; //마지막도시이면 지금까지값 저장.
			}
		}
		
		System.out.println(price);
	}

}