[자바] 백준 27315 - 틀리는 건 싫으니까 쉬운 문제에 올인하려고 합니다 (java)

 문제 : boj27315

---

 

필요 알고리즘 개념

• 그리디, 정렬
  
  • 보통 그리디가 붙으면 나머지 태그들은 그리디 규칙을 적용시키기 위해 사용된다. 이번에도 마찬가지다! 매번 최선의 문제를 선택해나가면 문제를 풀 수 있고, 최선의 문제를 선택하기 위해 정렬이 필요하다.

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

 

---

 

풀이

  

  우선 T와 E가 주어지지 않는다고 가정하고 생각해보자.

이 경우 간단한데, 매번 HD 이하의 D값을 가진 문제들 중에 P가 가장 작은순서대로 선택해주면 끝이다.

그럼 T가 1인 경우 어떻게 처리하면 될까? 틀렸습니다를 받지 않는다고 했으므로 단순히 해당 문제의 P = 0 이라 생각하면 된다. E가 1인 경우는 해당 문제의 D와 P가

라고 생각하면 된다. 문제에서는 D/2의 내림이라고 했는데, 왜 올림으로 생각해야하냐고 할 수 있다.

문제에서 나온 왜냐면 HD 이하의 D를 가진 값이라면, 그 수치가 몇이되든 전혀 상관 없기 때문이다. 우리가 중요한건 HD와 D를 기준으로 아무튼 해당 문제를 풀 수 있냐는거다. 그리고 E=1인 문제의 경우 지문에서 'HD x 2 >= D'인 경우에 풀 수 있다고 했다. 'HD x 2 >= D'가 가능하려면 D/2를 올림한 수치보다 HD가 크거나 같아야 한다. 따라서 D/2를 올림한 수치로 문제의 D를 변경해주면 된다.

 

  T와 E일 때의 처리가 끝났다면, 풀이법은 처음과 동일하다. T와 E까지 적용된 D와 P값을 가지고 매번 HD 이하의 D값을 가진 문제들 중에 P가 가장 작은순서대로 선택해주면 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

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

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        PriorityQueue<int[]> candidates = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            if (t==1) p = 0;
            candidates.add(e==1 ? new int[]{d/2+d%2,p/2} : new int[]{d,p});
        }
        st = new StringTokenizer(br.readLine());
        int hd = Integer.parseInt(st.nextToken());
        int hp = Integer.parseInt(st.nextToken());

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long wa = 0;
        while (m-->0) {
            while (!candidates.isEmpty() && candidates.peek()[0] <= hd) pq.add(candidates.poll()[1]);
            
            if (pq.isEmpty()) {System.out.println(-1); return;}
            int p = pq.poll();
            if (p>hp) wa += p-hp;
            hd+=1; hp+=1;
        }
        System.out.println(wa);
    }
}