백준 알고리즘 그리디 뽀개기 (Java) - 총 9문제
www.acmicpc.net/workbook/view/3977
문제집: 알고리즘 중급 1/3 (baekjoon)
www.acmicpc.net
710 - 그리디 알고리즘
1
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
import java.io.FileInputStream;
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(), K = sc.nextInt();
int[] coinType = new int[N];
for(int i = 0; i < N; i++)
coinType[i] = sc.nextInt();
int count = 0;
for(int i = N - 1; i >= 0; i--) {
if(coinType[i] <= K) {
count += K / coinType[i];
K %= coinType[i];
}
}
System.out.println(count);
}
}
2
1931번: 회의실배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int[][] time = new int[N][2];
for(int i = 0; i < N; i++) {
time[i][0] = scan.nextInt(); // start time
time[i][1] = scan.nextInt(); // end Time
}
Arrays.sort(time, Comparator.comparingInt(o -> o[0])); // 필수
Arrays.sort(time, Comparator.comparingInt(o -> o[1]));
int cnt = 0;
int prevEndTime = Integer.MIN_VALUE;
for(int i = 0; i < N; i++) {
if(prevEndTime <= time[i][0]) {
cnt++;
prevEndTime = time[i][1];
}
}
System.out.println(cnt);
}
}
3
11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int[] time = new int[N];
for(int i = 0; i < N; i++) {
time[i] = scan.nextInt();
}
Arrays.sort(time);
int sum = 0;
for(int i = 0; i < N; i++) {
sum += time[i] * (N-i);
}
System.out.println(sum);
}
}
4
로그인
www.acmicpc.net
5
2138번: 전구와 스위치
N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1<i<n)번 스위치를="" 누르면="" i-1,="" i,="" i+1의="" 세="" 개의="" 전구의="" 상태가="" 바뀐다.="" 즉,="" 꺼<="" p=""> </i<n)번>
www.acmicpc.net
6
1285번: 동전 뒤집기
첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위
www.acmicpc.net
7
1202번: 보석 도둑
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci
www.acmicpc.net
8
2109번: 순회강연
한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에
www.acmicpc.net
9
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
