[백준/28070] 유니의 편지쓰기 - JAVA

📌 문제

알고리즘 분류 : 누적합, DP
난이도 : 골드5
출처 : 백준 - 유니의 편지쓰기

🦧 문제 풀이 접근

9999년 12월까지 담을 수 있는 배열을 선언.
입력받은 입대월 index에 +1, 전역월 index+1에 -1.
해당 값을 누적하면서 가장 큰 값과 해당 index를 찾는다.

💻 code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[120_002];
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " -");
            int year1 = Integer.parseInt(st.nextToken());
            int month1 = Integer.parseInt(st.nextToken());
            int year2 = Integer.parseInt(st.nextToken());
            int month2 = Integer.parseInt(st.nextToken());
            dp[year1*12+month1]++;
            dp[year2*12+month2+1]--;
        }
        int maxPeople=0;
        int maxDay=0;
        for(int i=24_000;i<dp.length;i++) {
            dp[i] += dp[i-1];
            if(maxPeople<dp[i]) {
                maxPeople = dp[i];
                maxDay = i;
            }
        }
        if(maxDay%12==0)
            System.out.print(maxDay/12-1+"-"+12);
        else if(maxDay%12<10)
            System.out.println(maxDay/12+"-0"+maxDay%12);
        else
            System.out.print(maxDay/12+"-"+maxDay%12);
    }
}

🥇 결과

🎓 느낀점

처음에 전역월-입대월 만큼 반복문을 돌리니 시간 초과가 발생했다. DP 개념과 누적합 개념을 적절히 사용해서 해결했다.