[JAVA] 백준 2457 공주님의 정원

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

농담 아니고, 이 사진 위에도 틀린 코드가 30개는 족히 있다.

 

군자의 복수는 10년이 걸려도 늦지않는다. 문제 해결을 실패하고, 2년 좀 안되는 시점에 다시 시도해서 성공했다! 너무 기쁘다!!!

문제분석

어쩌면 살짝 억울하다고 느끼는 점은, 아이디어 자체는 2년 전 시도와 완벽하게 동일하다. 단지 언어 변경과 그리디 알고리즘에 대한 공부(이게 가장 큰 것 같긴 하다)를 통해 생각보다 쉽게 해결하였다.

사실 쉬운 정도가 아니라, 2년 전 시도 코드와 비교하면 말도 안되게 짧다. 부분 문제의 최적해를 이어서 전체 문제의 최적해로 나아간다는 아이디어를 통해 대폭 줄인 것 같다.

 

좌측이 2년 전 모든 예외처리를 하며 for문을 도는 시도를 한 코드이고, 우측은 이번에 작성한 정답 코드이다.

 

풀이는 다소 간단하다. 꽃을 심으면서, 다음 조건을 만족하면 된다.

 

1. 직전의 꽃이 죽기 전에 피는 꽃들 중 하나를 무조건 골라야 함.

2. 직전의 꽃이 죽는 시점부터 계산했을 때, 가능한 한 오래 살아있는 꽃을 골라야 함.

 

이 조건을 만족하면서, 꽃이 살아있는 시점이 1130을 초과하는 경우에 반복문을 break한다.

꽃이 살아있는 시점이 1130 이하인 경우 count 값을 0 으로 초기화한다(불가능하다는 뜻).

코드

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

public class Main{
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];// [시작일, 종료일], [시작일, 종료일]...

        // 0301~1130 채워야 함. 
        // 이어진 꽃들 중 '가장 수명이 긴' 꽃들을 선택해 나아가기

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

            String startMonth = st.nextToken();
            String startDay = st.nextToken();
            if(startMonth.length()<2)startMonth = "0" + startMonth;
            if(startDay.length()<2)startDay = "0" + startDay;

            String endMonth = st.nextToken();
            String endDay = st.nextToken();
            if(endMonth.length()<2)endMonth = "0" + endMonth;
            if(endDay.length()<2)endDay = "0" + endDay;

            arr[i][0]=Integer.parseInt(startMonth+startDay);
            arr[i][1]=Integer.parseInt(endMonth+endDay);
        }
        Arrays.sort(arr,(a,b)->{
            if(a[0]!=b[0]){
                return a[0]-b[0];
            }else{
                return b[1]-a[1];
            }
        });

        int start = 301;
        int tempStart = 0;
        int tempLast = 0;
        int greatLast = 301;
        int count = 0;
        
        for(int i = 0; i<N ; i++){
            tempStart = arr[i][0];
            tempLast = arr[i][1];

            if(tempStart > start){ // 꽃 배치해야 할 때
                start = greatLast;
                count++;
            }

            if(tempLast >= greatLast && start >= tempStart){ // 현재 최대 범위 꽃보다 더 오래 살아남을 경우 업데이트
                greatLast = tempLast;
            }

            if(greatLast>1130)break; // 1130을 넘겼음면, 더이상 확인할 필요 없음

        }
        count++;
        if (greatLast<=1130)count=0;
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }
}