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

군자의 복수는 10년이 걸려도 늦지않는다. 문제 해결을 실패하고, 2년 좀 안되는 시점에 다시 시도해서 성공했다! 너무 기쁘다!!!
문제분석
어쩌면 살짝 억울하다고 느끼는 점은, 아이디어 자체는 2년 전 시도와 완벽하게 동일하다. 단지 언어 변경과 그리디 알고리즘에 대한 공부(이게 가장 큰 것 같긴 하다)를 통해 생각보다 쉽게 해결하였다.
사실 쉬운 정도가 아니라, 2년 전 시도 코드와 비교하면 말도 안되게 짧다. 부분 문제의 최적해를 이어서 전체 문제의 최적해로 나아간다는 아이디어를 통해 대폭 줄인 것 같다.


풀이는 다소 간단하다. 꽃을 심으면서, 다음 조건을 만족하면 된다.
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();
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 12100 2048(Easy) (0) | 2025.07.21 |
|---|---|
| [JAVA] 백준 9663 N-Queen (1) | 2025.07.16 |
| [JAVA] 백준 16946 벽 부수고 이동하기 4 (2) | 2025.07.15 |
| [JAVA] 백준 2667 단지번호붙이기 (0) | 2025.07.14 |
| [JAVA] 백준 2322 아령 (0) | 2025.07.08 |