사용자 도구

사이트 도구


ps:problems:boj:11052

카드 구매하기

ps
링크https://www.acmicpc.net/problem/11052
출처BOJ
문제 번호11052
문제명카드 구매하기
레벨실버 1
분류

DP

시간복잡도O(n^2)
인풋사이즈n<=1000
사용한 언어Python
제출기록29200KB / 112ms
최고기록88ms
해결날짜2021/12/28

풀이

  • 간단한 DP 문제
  • DP[i]를 카드 i장을 가장 비싸게 구입하는 가격이라고 하면, 점화식은 아래처럼 나온다
    • $ DP[0] = 0 \\ DP[x] = \max_{0 \leq i < x}{DP[x-i] + P_i} $
  • 점화식대로 DP테이블을 채워나가면서 계산하면 총 시간복잡도는 O(n^2)

코드

"""Solution code for "BOJ 11052. 카드 구매하기".

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

Tags: [DP]
"""


def main():
    N = int(input())
    P = [int(x) for x in input().split()]

    dp = [0]
    for _ in range(N):
        dp.append(max(dp_i + p_j for dp_i, p_j in zip(reversed(dp), P)))

    print(dp[-1])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
B C A V J
 
ps/problems/boj/11052.txt · 마지막으로 수정됨: 2021/12/31 08:35 저자 teferi