[자바] 백준 20207 - 달력 (java)

 문제 : boj20207

---

 

필요 알고리즘 개념

• 그리디
  
  • 매번 통하는 일정한 규칙을 정해서, 해당 규칙을 따르면 원하는 답을 구할 수 있는걸 말한다. 보통 엄밀히 증명되기 보다는 '이렇게 하면 될 것 같은데?' 라고 해서 시도해보고 맞는 경우가 많다. 딱히 방법이 정해진 알고리즘이 아니고, 개념적인 거니 알아야 풀 수 있고 그런건 아니다.

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

 

---

 

풀이

  이 문제는 문제에서 제시된대로 시뮬레이션 문제인 것 처럼, 제시된 규칙을 완벽히 따라서 구현해도 통과될 정도로 시간이 널널한 문제긴 하다.

 

 

  하지만 더 쉽게 풀 순 없을지 한번 생각해보자. 이 문제에서 중요한건 결국 

 

1. 일정이 연속된 일자들의 그룹

2. 각 그룹마다 최대 일정 수를 가진 날의 일정 수

 

이렇게 2가지 이다.

 

 

  우선 '1'은 대충 생각해봐도 어떻게 놓던지 일정의 기간을 바꿀 순 없으니 절대 바뀌지 않을 것임을 알 수 있다. 예를들어 저 두개를 옮긴다고 해도, 연속된 일자들의 그룹(2~9일 / 11~12일)은 변경되지 않는걸 볼 수 있다. 다만 이렇게 변경은 못하는데, '일정은 가능한 최 상단에 배치된다.' 라는 규칙 때문이다.

 

 

  또한 각 그룹마다 최대 일정 수를 가진 날의 일정 수도 마찬가지인데, 어차피 겹치지 않으면 '일정은 가능한 최 상단에 배치된다.'에 따라 맨 위로 올라가야 하고, 겹친날은 뭔짓을 하던 겹친다. 즉, 아래와 같이 그냥 겹친날은 겹친거고 다른 날은 잘라서 맨 위로 올려버리던 뭐하던 가장 일정 수가 많이 겹친날만 중요하다.

 

 

 

  이게 뭘 의미하냐면 그냥 해당 날짜에 있는 일정의 갯수만 세주면 된다는 것이다.

날마다 카운팅해준 후, 카운트가 '0'인 날을 기준으로 구간을 나눠서 각 구간마다의 최대 카운트 수와 구간의 수를 구해주면 된다. 따라서 답은 3x8 + 2x2 = 28이 된다.

 

 

---

 

코드 : github

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

public class Main {
    private static final int DAY_OF_YEAR = 365;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] cnt = new int[DAY_OF_YEAR+1];
        while (n-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            for (int i = s; i <= e; i++) {
                cnt[i]++;
            }
        }

        int sum = 0;
        int maxHeight = 0;
        int width = 0;
        for (int i = 0; i <= DAY_OF_YEAR; i++) {
            if (cnt[i] == 0) {
                sum+=maxHeight*width;
                maxHeight = width = 0;
                continue;
            }
            width++;
            maxHeight = Math.max(maxHeight, cnt[i]);
        }
        sum+=maxHeight*width;
        System.out.println(sum);
    }

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