Barbera

www.acmicpc.net/problem/2031 2031번: 이 쿠키 달지 않아! 첫 번째 줄에 4개의 자연수 T, N, D, K가 주어집니다. (1 ≤ T ≤ 109, 1 ≤ N ≤ 106, 1 ≤ D ≤ 109, 1 ≤ K ≤ 10) 두 번째 줄에 N 종류의 음식 각각을 먹을 시각을 나타내는 N 개의 자연수 a1, ..., aN이 주어집 www.acmicpc.net 재미있는 DP문제였습니다. 다이어트 효과가 최대가 되려면 다이어트가 효과가 유지되는 시간안에 음식이 가장 많이 포함되어 있어야 합니다. 우선 단순하게 K=1일때의 문제를 생각해 봅시다. 위에서 정의한 문제를 'D만큼의 범위안에 포함할 수 있는 원소의 최대 개수'로 치환할 수 있습니다. 그렇다면 이 문제는 정렬과 이분탐색을 이용하면 O(..