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

접근

다이나믹 프로그래밍을 이용해서 풀 수 있다.

하지만, 동시에 볼 수 있는 애니메이션 K의 범위가 100,000이므로 1, 2, 3 더하기 5 문제처럼 모든 경우의 수를 따지면 바로 시간초과다.

주요 아이디어

• N개의 애니메이션을 K개씩 볼 수 있을 때, 길이가 가장 긴 애니메이션 부터 K개씩 그룹을 나누어 보는 것이 가장 짧은 시간에 볼 수 있는 방법이다.

• 다이나믹 테이블(dp[i])는 i+1개의 애니메이션을 볼 수 있는 최소 시간이다.

풀이

1. 우선 애니메이션 리스트(a)를 입력받아 정렬해주어야 한다.

2. 전체 애니메이션 N까지 range(0, N)의 반복문을 돌면서 i를 매개 변수로 받는 함수로 dp[i]의 값을 구한다.

3. i+1개의 애니메이션을 봤을 때 i < K 라면 dp[i] = a[i] 이다.

4. i >= K 라면, dp[i] = dp[i-K] + a[i] 이다.
   • 가장 긴 시간부터 4개씩 그룹 짓는 것이 항상 이득이므로 항상 dp[i-4]에서 자신을 더한 값이 dp[i]가 된다.
5. return된 값이 애니메이션을 볼 수 있는 시간 M보다 작다면 dp에 해당 값을 추가한다. M보다 크다면 즉시 반복문을 빠져나오고 답을 출력한다.

코드

import sys
input = sys.stdin.readline

def get_time(i):
    time = 2147000000
    if i < K:
        return animations[i]
    else:
        return dp[i-K] + animations[i]
    

N, M, K = map(int, input().split())
animations = list(map(int, input().split()))
animations.sort()

dp = []

for i in range(N):
    time = get_time(i)
    if time > M:
        break
    else:
        dp.append(time)
        
print(len(dp))