[JAVA]백준 20207번: 달력

 

https://www.acmicpc.net/problem/20207

20207번: 달력

 

1. 문제 설명

 

 

2. 풀이

 

dp 배열을 이용하여 풀 수 있다.

 

주어진 일정이 x,y라고 할 때 dp[x]를 1 증가시키고, dp[y+1]을 1 감소시킨다.

 

dp[x]를 1 증가시켜줌으로 x부터 일정이 한개가 시작함을 의미하고, dp[y+1]을 1감소시켜 줌으로 일정이 y일에 끝났음을 의미한다.

 

이러한 과정을 통해 dp배열을 앞에서 부터 더해가면서 x일의 일정의 개수를 구할 수 있다.

 

x가 2, y가 4라고 했을 때 2부터 5까지 dp배열을 그려본다면 아래와 같다.

 

1

0

0

-1

 

앞에서 부터 dp 배열을 더해간다면 어떻게 될까? 

 

2일은 하나의 일정을 가지고 있다 (dp[2]=1)

3일은 하나의 일정을 가지고 있다 (dp[2]+dp[3]=1)

4일은 하나의 일정을 가지고 있다.(dp[2]+dp[3]+dp[4]=1)

5일은 0개의 일정을 가지고 있다. (dp[2]+dp[3]+dp[4]+dp[5]=0)

 

일정의 개수와 dp배열을 더한 값이 일치하는 것을 볼 수 있다.

 

이러한 방식을 이용해 x부터 y일까지 일정이 있을 때 x부터 y일까지 다 1씩 일정을 추가해주지 않더라도, 최대 일정의 개수를 구할 수 있다.

 

이를 이용해 연속되는 구간의 길이와 그 구간의 최대 일정의 개수을 곱해 answer에 저장해 나가면 된다.

 

 

3. 코드

// JAVA 11, 시간 140ms, 메모리 14532KB
// dp 배열을 합해가면서 현재 x 날짜의 일정의 개수를 구한다.
// 연속되는 구간을 구하고, 연속되는 구간 * 연속되는 구간의 최대 일정의 개수를 answer 변수에 더한다.
// 일정의 시작 날짜를 s, 끝나는 날짜를 e라고 하면
// dp[s]++, dp[e+1]--를 수행한다.
// dp[s]에 1을 더하는 것은 dp[s]부터 일정이 하나 더 추가 되었다는 것을 의미하고,
// dp[e+1]에 1을 감소하는 것은 dp[e]까지만 일정이 하나 더 추가되었다는 것을 의미한다.
// e+1부터는 일정이 1 추가되지 않았기에 감소하여 일정이 e까지만이었다는 것을 나타낸다.

import java.io.*;
import java.util.*;


public class Main {


    public static int planNum;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        planNum = Integer.parseInt(br.readLine());

        // 일정의 날짜 범위 1 - 365, e+1 구현위해 366까지 idx 존재해야 함.
        int[] dp = new int[367];

        for (int x = 0; x < planNum; x++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            dp[Integer.parseInt(st.nextToken())]++;
            dp[Integer.parseInt(st.nextToken()) + 1]--;
        }

        int prevDay = 0;
        int maxPlan = 0;
        int sum = 0;
        int answer = 0;

        for (int x = 0; x <= 366; x++) {
            sum += dp[x];

            // 최대 일정 개수
            maxPlan = Math.max(maxPlan, sum);


            // 연속되는 일정이 처음 시작될 때 -> prevDay에 현재 날짜 저장
            if(prevDay==0 && sum!=0){
                prevDay=x;
            } else if (prevDay!=0 && sum == 0) {
                // 연속되는 일정이 끝날때
                // 연속되는 구간 길이 * 최대 일정의 개수
                answer += (x - prevDay) * maxPlan;
                // 초기화
                prevDay = 0;
                maxPlan = 0;
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();

    }



}