[자바] 백준 11912 - 격자 보존하기 (java)

목차

문제 : boj11912

 

 

필요 알고리즘

• 그리디 알고리즘
  
  • 규칙만 찾으면 쉽게 접근 가능하다.

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

 

 

풀이

  아이디어만 떠오르면 어렵지 않은 문제이다. 말이 있을 때, 격자를 놓을 수 있는 경우의 수를 생각해보자. 사실 이것만 생각나면 끝인 문제이다.

 

1. 첫 번째 말 앞에 1개의 격자를 두는 경우 -> 문제 내에서 1번만 가능

2. 마지막 말 뒤에 1개의 격자를 두는 경우 -> 문제 내에서 1번만 가능

3. 말과 말 사이에 2개의 격자를 두는 경우 -> 말이 k마리라면 k-1번 가능

 

  따라서 위에서 '1'과 '2'는 한번씩만 가능하므로, 칸막이 수 d가 특정 수치까지 남을 때까지는 최대 k-1번 가능한 '3'을 진행해주면 된다. 이 경우 k-1개의 '3'의 경우 중 어떤걸 선택해야 할까? 간격이 큰거부터 계속 골라나가면 된다! '특정 수치'는 몇일까? 3이하로 남기 전까지 진행하면 된다.

long sum = 0;
while (d>3 && !pq.isEmpty()) {
    sum+=pq.poll();
    d-=2;
}

 

  왜 d=3 이하일 경우는 별도로 봐야 할까? 아래의 경우의 수가 있기 때문이다.

- d=1 인 경우 '3'은 진행이 불가하다. '1'과 '2' 중 큰 쪽을 선택해야 한다.

- d=2 인 경우 '1'+'2' 와 '3'을 더 진행하는 것 중 큰 쪽을 선택해야 한다.

- d=3 인 경우 '3'+'1' 과 '3'+'2'와 '1'+'2' 중 큰 쪽을 선택해야 한다.

if (d==1) {
    sum += Math.max(s, e);
} else if (d==3) {
    sum += Math.max(s+e, pq.isEmpty()?0:pq.poll()+(Math.max(s,e)));
} else {
    sum += Math.max(s+e, pq.isEmpty()?0:pq.poll());
}

 

 

코드 : github

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

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

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

        st = new StringTokenizer(br.readLine());
        long cur = Integer.parseInt(st.nextToken());
        long s = cur-1;
        if (s < 0) s = 0;

        PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
        while (--k>0) {
            long tmp = Integer.parseInt(st.nextToken());
            pq.add(tmp-cur-1);
            cur = tmp;
        }

        long e = n-cur;

        long sum = 0;
        while (d>3 && !pq.isEmpty()) {
            sum+=pq.poll();
            d-=2;
        }

        if (d==1) {
            sum += Math.max(s, e);
        } else if (d==3) {
            sum += Math.max(s+e, pq.isEmpty()?0:pq.poll()+(Math.max(s,e)));
        } else {
            sum += Math.max(s+e, pq.isEmpty()?0:pq.poll());
        }

        System.out.println(sum);
    }
}