1. 개념
현재 상황에서 지금 가장 좋은 것만 고르는 방법
매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해 고려하지 않음
‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준이 있음
예제 3-1) 거스름돈
문제
거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라.
풀이
큰 순서로 거슬러 준다.
거스름돈 배열에 큰 순서대로 선언을 해두고, 현재 금액(N)에서 거슬러줄 수 있는 만큼 거슬러 주고, 남은 금액은 그 다음 거스름돈으로 거슬러준다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Greedy1 {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bufferedReader.readLine());
int[] money = {500, 100, 50, 10};
int result = 0;
for (int i = 0; i < money.length; i++) {
result += N/money[i];
N %= money[i];
}
System.out.println(result);
}
}
정당성
위의 예제에서는 가지고 있는 동전에서 큰 단위가 항상 작은 단위의 배수이므로, 그리디로 해결할 수 있다. 하지만 500, 400, 100원과 같이 배수가 아닐 때는 사용할 수 없다. (ex. 800원인 경우 그리디에 따르면 500+100+100+100인데, 400+400이 최소가 되기 때문) 따라서 문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 답을 도출할 수 있다.
2. 실습
큰수의 법칙
문제
큰수의 법칙
다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 (단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징)
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력해보기
풀이
제일 큰 수를 K번, 두번째 큰수를 1번, 다시 제일 큰수를 K번, .. 이렇게 반복하면 가장 큰 수를 만들 수 있다.
교재보고 이해 -> 제일 큰 수를 더하는 횟수를 구한다. {M/(K+1)}*K + M%(K+1)
코드
import java.util.Arrays;
import java.util.Scanner;
public class Greedy2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[] nums = new int[N];
for (int i = 0; i < N; i++) {
nums[i] = sc.nextInt();
}
Arrays.sort(nums);
int result = 0;
int offset = 0;
while(M>0){
int cnt = 0;
int index = 0;
if (offset % 2==0){
index = N-1;
if (M>=K){
cnt = K;
} else{
cnt = (M%K);
}
} else{
index = N-2;
cnt = 1;
}
result += nums[index] * cnt;
M -= cnt;
offset += 1;
}
System.out.println(result);
}
}import java.util.Arrays;
import java.util.Scanner;
public class Greedy2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[] nums = new int[N];
for (int i = 0; i < N; i++) {
nums[i] = sc.nextInt();
}
Arrays.sort(nums);
int count = (M/(K+1))*K + M%(K+1);
int first = nums[N-1] * count;
int second = nums[N-2] * (M-count);
int result = first + second;
System.out.println(result);
}
}숫자 카드 게임
문제
가장 높은 숫자가 쓰인 카드를 뽑아야 한다. N*M 형태로 숫자카드가 놓여져있다. 선택한 행에서 가장 숫자가 낮은 카드를 뽑아야 한다. 최종적으로 가장 높은 숫자 카드를 뽑을 수 있도록 해야한다.
ex) 아래의 카드에서는 첫번째, 두번째 행을 선택하면 1을 뽑아야 하므로 세번째 행을 선택하여 2를 뽑는 것이 정답이다.
3 1 2
4 1 4
2 2 2
풀이
처음에는 입력받은 값을 배열에 저장하는 방법을 사용했다. 배열에 값을 오름차순으로 둬 인덱스가 0인 값을 리스트에 넣고 가장 큰 값 출력
한줄씩 입력 받는다면 굳이 배열에 저장할 필요는 없고, 변수에 저장해서 할 수 있다는 생각을 했다. -> 결과값을 저장해두는 변수를 두고, 각 행마다 가장 작은 값과 결과값을 비교하여 더 큰 값을 결과값에 저장
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Greedy3 {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String string = bufferedReader.readLine();
int N = Integer.parseInt(string.split(" ")[0]);
int M = Integer.parseInt(string.split(" ")[1]);
List<Integer> nums = new ArrayList<>();
for (int i = 0; i<M; i++){
String numString = bufferedReader.readLine();
List<Integer> numList = new ArrayList<>();
for (int j = 0; j<N; j++){
numList.add(Integer.parseInt(numString.split(" ")[j]));
}
Collections.sort(numList);
nums.add(numList.get(0));
}
nums.sort(Collections.reverseOrder());
System.out.println(nums.get(0));
}
}
1이 될 때까지
문제
- N에서 1을 뺀다
- N을 K로 나눈다
위의 두 방법으로 1이 되는 최소 횟수를 구한다.
풀이
가장 많이 나눌 수 있을 때 최소 횟수가 될 것이라고 생각했다.
N이 K로 나누어지면 몫만큼 더하고, 아니면 1 더한 후 N에서 1을 뺀다.
(예외가 있나?)
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Greedy4 {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String string = bufferedReader.readLine();
int N = Integer.parseInt(string.split(" ")[0]);
int K = Integer.parseInt(string.split(" ")[1]);
int result = 0;
while(true){
if (N%K == 0){
result += N/K;
break;
} else {
N -= 1;
result += 1;
}
}
System.out.println(result);
}
}