그리디 알고리즘

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

문제

https://www.acmicpc.net/problem/11047

내풀이

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

public class B11047 {
	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[] arr = new int[n];
		
		int count=0;
		
		for (int i = 0; i < n; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		
		for (int i =n-1; i >=0; i--) {
			if(arr[i]<=k) { //가진돈보다 작으면
				count =count+(k/arr[i]); //몫을 카운터에 추가
				k=k%arr[i]; //나머지는 나눠서 계속
			}
		}
		
		System.out.println(count);
		
	}
}

문제

https://www.acmicpc.net/problem/1931

내풀이

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

public class B1931 {
	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[][] arr= new int[n][2];
		
		for (int i = 0; i < arr.length; i++) {
			st = new StringTokenizer(br.readLine());
			int start= Integer.parseInt(st.nextToken());
			int end= Integer.parseInt(st.nextToken());
			arr[i][0] =start;
			arr[i][1] =end;
			}	
		Arrays.sort(arr,new Comparator<int []>() { //{1,2}와 {2,2}를 비교하므로 <int []>

			@Override
			public int compare(int[] o1, int[] o2) {  
				if (o1[1] ==o2[1]) { //{1,2}에서 2와 {2,2}에서 2를 비교해서 같으면 즉 끝나는시간이 같으면
				return o1[0]-o2[0]; 	// 출발시간을 기준으로 정렬
				}
				return o1[1]-o2[1]; 	// 끝나는시간을 기준으로 정렬
			}		
		});
		int end = -1;
		int count= 0;
		for (int i = 0; i < arr.length; i++) {
			if(end<=arr[i][0]) { //시작시간과 끝나는 시간이 같을 수도 있으니 <=
				end=arr[i][1];
				count++;
			}
		}
		System.out.println(count);
			
		}
	}

해설

현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는게 유리하다. 그렇기 때문에 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택

주의: 종료 시간이 같을경우
예를들어 (2,2)와 (1,2) 2개의 회의가 잇다고 가정했을때 (2,2)를 먼저 배정하고 (1,2)를 배정하면 오류가 생긴다.
따라서 종료 시간이 같으면 시작 시간이 빠른 순서로 정렬하는 로직도 추가해야한다.

Compare()함수 사용법:

Arrays.sort(arr,new Comparator<int []>() { //{1,2}와 {2,2}를 비교하므로 <int []>

			@Override
			public int compare(int[] o1, int[] o2) {  
				if (o1[1] ==o2[1]) { //{1,2}에서 2와 {2,2}에서 2를 비교해서 같으면 즉 끝나는시간이 같으면
				return o1[0]-o2[0]; 	// 출발시간을 기준으로 정렬
				}
				return o1[1]-o2[1]; 	// 끝나는시간을 기준으로 정렬
			}		
		});