사용자 도구

사이트 도구


ps:problems:boj:14728

벼락치기

ps
링크acmicpc.net/…
출처BOJ
문제 번호14728
문제명벼락치기
레벨골드 5
분류

DP

시간복잡도O(nW)
인풋사이즈n<=100, W=10000
사용한 언어Python 3.11
제출기록31256KB / 116ms
최고기록116ms
해결날짜2023/08/31

풀이

  • 전형적인 0-1 knapsack 문제. 무게(=공부시간)의 합이 배낭 용량(=남은 시간)을 초과하지 않으면서 가치(=점수)합을 최대화 시키도록 물건(=과목)들을 선택하면 하면 된다
  • 풀이는 평범한 배낭 참고.
  • 다만 평범한 배낭과는 n=100, w_i<1000인 것은 똑같지만, W가 100,000과 10,000으로 차이가 있다. W=100,000 이었던 평범한 배낭은 실제로 가능한 무게합들이 스파스해서 dict를 써서 dp table을 만드는 편이 더 효율적이었지만, W=10,000인 이 문제에서는 그냥 list로 dp table을 만드는것이 더 효율적이다.

코드

"""Solution code for "BOJ 14728. 벼락치기".

- Problem link: https://www.acmicpc.net/problem/14728
- Solution link: http://www.teferi.net/ps/problems/boj/14728

Tags: [knapsack] [dp]
"""

import sys


def main():
    N, T = [int(x) for x in sys.stdin.readline().split()]
    K_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    dp = [0] * (T + 1)
    for k, s in K_and_S:
        for t, dp_t, dp_p in zip(range(T + 1), dp, dp[k:]):
            if dp_p + s > dp_t:
                dp[t] = dp_p + s

    print(max(dp))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
M G R O L
 
ps/problems/boj/14728.txt · 마지막으로 수정됨: 2023/08/31 12:49 저자 teferi