[자바] 백준 25496 - 장신구 명장 임스 (java)

 문제 : boj25496

---

 

필요 알고리즘 개념

• 그리디
  • 특정 규칙을 정해 매번 해당 규칙을 따라가면 결과가 구해지는 그리디 문제이다.
• 정렬
  
  • 정렬 하는 방법을 알아야 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  백준 자바러의 전설 임스님이 만든 문제이다. 남은 피로도가 200-P가 있고, N개의 정수 Ai가 주어진다. 200-P의 피로도 내에서 가장 많은 Ai 들을 선택하면 된다. 어차피 Ai들마다 별다른 가중치 같은게 없으므로, 단순하게 200-P를 다 쓸때까지 가장 낮은 Ai를 계속 고르면 된다. 따라서 그리디 문제이고, 가장 낮은 Ai를 고르기 위해 정렬이 필요하다.

 

  사실 N이 최대 1000밖에 안되므로, 정렬을 하지 않아도 매번 가장 낮은 값을 찾아도 O(N^2)에 통과가 가능하므로, 대강 가장 낮은것을 계속 고르는게 '제작할 수 있는 장신구의 최대 개수'라는 점만 알면 되는 혜자스러운 문제이다.

 

  이하 코드의 로직은 결론적으로 위에 설명한 바와 동일하다.

1. Ai 들을 정렬한다. (Arrays.sort())

2. p<200인 동안 피로도에 매번 가장 낮은 피로도를 더하면서 갯수를 센다. (cnt++, p+=arr[i++])

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        while (n-->0) arr[n] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);
        int cnt = 0;
        int i = 0;
        while (p<200 && i<arr.length) {
            cnt++;
            p+=arr[i++];
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}