백준 11047번 문제

풀이

• N개의 동전 종류가 있고 가치의 합 K를 입력 받은 후 다음 줄에는 동전의 가치 A(i) 오름차순으로 정렬해야 하는 문제 (동전의 가치는 배수로 입력)
• 문자열을 사용한 Greedy Algorithm(탐욕 알고리즘)을 사용해 해결하는 문제
• Greedy Algorithm 사용 안할 시 시간 복잡도 多

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int result = 0;
        int medeium = 0;
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken());
        int[] coin = new int[N];

        for (int i = 0; i < N; i++) {
            coin[i] = Integer.parseInt(bf.readLine());
        }
        Arrays.sort(coin);

        for (int i = N - 1; i >= 0; i--) {
            medeium = K / coin[i];
            K %= coin[i];
            result += medeium;
            if (K == 0) break;
        }
        bw.write(result + " ");
        bw.flush(); bf.close();
        bw.close();
    }
}

1. 입력 설정 및 정렬

int result = 0;
int medeium = 0;
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken());
int[] coin = new int[N];
for (int i = 0; i < N; i++) {
    coin[i] = Integer.parseInt(bf.readLine());
}
Arrays.sort(coin);

• 동전의 개수 입력 받을 N과 동전의 가치 입력 받을 K, 동전 종류 입력 받을 coin 배열 설정
• 동전은 오름차순으로 정렬해야 하므로 Arrays.sort([변수 이름]) 설정

2. Greedy Algorithm

for (int i = N - 1; i >= 0; i--) {
    medeium = K / coin[i];
    K %= coin[i];
    result += medeium;
    if (K == 0) break;
}
bw.write(result + " ");
bw.flush(); bf.close();
bw.close();

• 반복문을 사용해 큰 숫자부터 반복문 start
• 만일 다음 코인의 종류 중 하나가 더 이상 나눌 숫자가 없다면 break

총총

• 간단한 문제이지만 Greedy Algorithm을 사용하지 않으면 실수가 나올 수 있는 문제
• 오름차순 정렬 후 반복문을 돌릴 수 있었기에 Greedy Algorithm 구현이 간단 할 수 있었음
• 더 완벽한 Greedy Algorithm을 위해 공간복잡도를 𝓞(N)에서 𝓞(1) 로 줄이는 고민이 필요한 문제