반응형
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
* 문제는 해당 게시물 참고바랍니다.
그리디 알고리즘이란
그리디 알고리즘은 흔히 탐욕 알고리즘이라고도 불리며 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 각 단계에서 한 선택이 최선의 선택을 한 것이길 바라고 전체적으로도 최선이길 바라는 알고리즘입니다.
해당 문제를 해결한 코드입니다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int [][]table = new int[n][2];
int count =0;
//입력받기
for(int i=0; i<n; i++){
for(int j=0; j<2; j++){
table[i][j] = scanner.nextInt();
}
}
//정렬
Arrays.sort(table, new Comparator<int[]>() {
@Override
public int compare(int[] table1, int[] table2) {
// 종료시간이 같을 경우 시작시간이 빠른순으로 정렬
if(table1[1] == table2[1]) {
return table1[0] - table2[0];
}
return table1[1] - table2[1];
}
});
//counting
int j=0;
for(int i=0; i<n-1; i++){
int tmp = table[j][1];
if(tmp <= table[i+1][0]){
count++;
j=i+1;
}
}
System.out.println(count+1);
}
}
이렇게 해결하였습니다.
여기서
System.out.println(count+1);
해당 코드에서 count+1을 한 이유는 최초의 선택을 배정 가능한 테이블의 수로 포함하기 위해서 입니다.
결과
반응형
'백준' 카테고리의 다른 글
[백준][JAVA]구간 합 구하기4(11659번) - 누적합 (0) | 2023.08.22 |
---|---|
[백준][JAVA]색종이 만들기(2630번) - 분할 정복 (0) | 2023.08.20 |
[백준][JAVA]평범한 배낭(12865번) - 다이나믹 프로그래밍, 배낭 문제 (0) | 2023.08.16 |
[백준][JAVA]스타트와 링크(14889번) - 백트래킹 algorithm 그리고 재귀의 이해 (0) | 2023.08.15 |
[백준][JAVA]하노이 탑 이동 순서(11729번) - 재귀 algorithm (0) | 2023.08.10 |