[백준 / 골드1] 17420 깊콘이 넘쳐흘러 (Java)

문제 보기

사용한 것

• 최대 컵라면 수를 구하기 위한 그리디
• 과제를 컵라면 수로 오름차순 하기 위한 우선순위 큐

풀이 방법

• 사용할 계획 날짜 오름차순 먼저, 같으면 남은 기한 오름차순 한다.
• 같은 사용 날짜 구간으로 묶어서 생각한다.
• input을 for 문 돌면서
  • 현재 유효기간보다 이전 구간의 최댓값이 더 크면
    • 현재 구간 사용날짜가 이전 구간의 최댓값보다 크면 preMax 교체
    • 연장 횟수 계산해서 answer에 더해줌
  • 현재 유효기간보다 이전 구간의 최댓값이 같거나 작으면
    • 연장할 필요 없음
  • 현재 기프티콘의 유효기간과 curMax 비교해서 교체
  • 다음 기프티콘으로 구간 변경됐는지 확인 후 preMax를 curMax로 교체

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int[][] input = new int[n][2];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            input[i][0] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            input[i][1] = Integer.parseInt(st.nextToken());
        }

        // 그리디
        Arrays.sort(input, (o1, o2) -> {
            // 사용할 계획 날짜 오름차순, 남은 기한 오름차순
            if (o1[1] == o2[1]) {
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });
        long answer = 0;
        int preMax = input[0][1];
        int curMax = -1;
        for (int i = 0; i < n; i++) {
            // 현재 유효기간보다 이전 구간의 최댓값이 더 크면
            if (preMax > input[i][0]) {
                // 현재 구간 사용날짜가 이전 구간의 최댓값보다 크면 교체
                if (preMax < input[i][1]) {
                    preMax = input[i][1];
                }

                // 연장 횟수 계산
                int cnt = ((preMax - input[i][0]) + 29) / 30;
                input[i][0] += (cnt * 30);

                answer += cnt;
            }

            // 현재 구간의 최댓값 찾기
            curMax = Math.max(curMax, input[i][0]);

            // 구간 변경되면 현재 구간 최댓값을 이전 구간 최댓값으로
            if (i + 1 < n && input[i][1] != input[i + 1][1]) {
                preMax = curMax;
            }
        }

        System.out.println(answer);

        br.close();
    }
}