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

그냥 정렬해서 구하면 되는 문제인줄 알았는데 생각보다
너무 어려웠다... -_-

풀이 아이디어

시청 시간을 저장한 배열 viewTime을 오름차순으로 정렬해
viewTime배열의 길이만큼 순회하면서 계산한다.
배열 dp[i]은 i까지의 애니메이션을 보는데 필요한 최소시간을 저장한다.
한 번에 볼 수 있는 애니메이션이 k개라면

i<k이면
dp[i] = viewTime[i]이고
i>=k이면
dp[i] = dp[i-k]+viewTime[i]이다.

작은 시간부터 k개씩 묶는 것이 가진 시간에서 가장 많이 볼 수 있는 경우의 수가 된다.
예를 들어보자.

[입력]
3 15 2
10 5 10
[출력]
3

viewTime = [5, 10, 10]이고
dp = [5, 10, 15]가 된다.

풀이 코드

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

public class _27313_yet{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken()); // n: 볼 애니메이션 갯수 1 ≤ N ≤ 100,000
        int m = Integer.parseInt(st.nextToken()); // m: 사용가능한 시간 0 ≤ M ≤ 10^9
        int k = Integer.parseInt(st.nextToken()); // k: 동시에 볼 수 있는 애니메이션 개수 1 ≤ K ≤ 100,000

        // n개의 애니메이션 보는 시간 입력
        st = new StringTokenizer(br.readLine(), " ");
        ArrayList<Integer> viewTime = new ArrayList<Integer>();
        for(int i=0;i<n;i++){
            int inputViewTime = Integer.parseInt(st.nextToken());
            // 사용가능한 시간보다 작거나 같은 애니메이션만 볼 수 있음
            if(inputViewTime <= m){
                viewTime.add(inputViewTime);
            }
        }
        Collections.sort(viewTime); // 오름차순 정렬
        // dp[i]: i번째 애니메이션까지 볼 수 있는 최소 시간
        ArrayList<Integer> dp = new ArrayList<Integer>(); 
        if(viewTime.size() == 0){
            System.out.println("0");
            return;
        }
        int time = 0;
        for(int i=0;i<viewTime.size();i++){
            time = (i<k) ? viewTime.get(i) : dp.get(i-k) + viewTime.get(i);        
            
            if(time > m){
                break;
            }
            else{
                dp.add(time);
            }
        }
        
        System.out.println(dp.size());
        br.close();
    }   
}