목표: X일에 최대 약효
N개의 약은 각각 d일 후 e만큼 약효 발현
N, X <= 100,000
d, e <= 10,000
----
입력 예시 1
4 5 // 약 4개, 5일 째 (N = 4, X = 5)
4 5. // 1번 약 - 4일 후 5만큼 약효 발현
4 3
3 2
3 1
출력 예시 1
10
1일 2일 3일 4일 5일
1번 2번 3번
0 0 0 5 10
---
(4, 5)랑 (4, 3)을 어떻게 1, 2일에 나눠서 먹게끔 구현할지 감이 안 잡히네
DP로 어케 풀 수 있음? 그리디 같기도 하고 LIS 같기도 하고
냅섹스 아니노?
넵색 맞지? 왜이렇게 햇갈리지
약 무제한임?
아니면 1개만?
약 1~10만개
정렬하고나서 부분합을 통한 이분탐색 문제같음
정렬 → 부분합 → 이분탐색 의견 고마워 한 번 풀어봐주면 더 고마울 거 같아!
그리디 아님? 날짜 빨리오는 약 순서대로 그리디하게 할당하면 될거같은데
그리디 맞음
날짜 1순위, 약효 2순위로 내림차순 정렬 → 그리디 하게 왼쪽부터 약 선택 → 더 이상 약 선택 불가능 하면 종료 이거구나 ㄱㅅㄱㅅ
아 이것도 아닌데...ㅠ
풀었다 내가 잘못 생각하고 있었네
고마워!!