(JAVA) 백준 2457번 : 공주님의 정원 -- [그리디]

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

2457번: 공주님의 정원

 

안녕하세요.

 

이 문제는 백준의 회의실 배정, 택배 문제와 유사한 그리디 알고리즘 문제입니다.

https://maivve.tistory.com/36

(JAVA) 백준 8980번 : 택배

 

 

핵심은 간단합니다.

3월 1일부터 11월 30일까지 하루라도 꽃이 피어있지 않으면 안되고, 중복되는 꽃의 개화기간이 되도록 짧거나 없어야합니다.

 

근데, 입력 날짜를 월/일 로 받기 때문에 이를 그대로 활용하는 것은 비효율적입니다.

 

처음에는 월/일 을 하나의 일 수로 계산해서 진행했지만, 이보다 더 편한 방법이 있었습니다.

MMDD 를 그대로 4자리의 숫자로 활용하면 됩니다.

ex) 3월 1일 -> 301, 11월 30일 -> 1130

 

 

다음으로,

개화시간이 3월 1일 이전에 시작해서 3월 1일을 지나는 꽃을 먼저 찾아 선택합니다.

 

먼저 찾아 선택하는 방법은 별도 클래스를 만들고, 이를 배열에 담아 Sort했습니다.

Sort의 조건은 Comparable 인터페이스를 구현했는데,

 

1) 시작일 낮은 순

2) 종료일 높은 순

 

으로 우선순위를 비교해 정렬했습니다.

 

그 이유는 날짜는 1월 -> 12월까지 순차적으로 진행되기 때문에, 가장 앞에서부터 하루하루 계산해가야하기 때문에

시작일이 낮은 순서대로 정렬해둬야 앞에서부터 하나씩 비교해가면서 꽃을 선택할 수 있습니다.

 

 

다음으로, 종료일이 높아야 해당 꽃이 더 길게 피어있으니 이를 선택하는 방법이 최선이기 때문입니다.

 

그렇게 꽃이 지는 기간이 12월 1일 이상까지의 꽃을 최후로 선택하면 됩니다.

왜냐하면, 입력 값에서 지는 기간을 12월 1일로 받은 경우에는 하루 전인 11월 30일까지 피어있다는 문제 설명이 있기 때문에 헷갈리면 틀립니다.

형광펜 참고!

 

 

 

다음으로 고려할 사항은

 

1) 이전에 선택한 꽃의 지는 기간 이후에 개화하는 꽃을 선택하면 안됩니다.

  -> 하루라도 공백이 생길 수 있기 때문에, 최대한 겹치는 부분이 작거나 지는 기간 다음날에 바로 개화하는 꽃을 찾아야 합니다.

 

2) 12월 1일까지만 찾으면 됩니다. 그 다음 기간의 꽃을 찾는것은 의미가 없고 낭비입니다.

3) 가장 오래 피어있는 꽃을 탐색해야합니다.

 

 

지금까지 적은 내용을 생각한 다음, 소스코드를 참고해주시면 더 빠르게 이해하실 수 있습니다.

(저도 해결했지만 더 효율적인 방법을 찾기 위해 다른 분들의 해설이나 정답을 참고해서 재구성했습니다..!)

 

 

 

감사합니다.

 

 

소스코드

---