nonneng.ee
Daeun-rithm
nonneng.ee
전체 방문자
오늘
어제
  • 분류 전체보기 (51)
    • Back-end (17)
      • Server (3)
      • Database (3)
      • Spring (9)
      • Node.js (1)
    • Book (1)
      • 이펙티브 자바 (0)
      • 대규모 시스템 설계 (1)
    • Algorithm (1)
      • Greedy, Implementation (6)
      • Dynamic Programming (5)
      • Data Structure (3)
      • Sorting (2)
      • Concept (1)
    • TIL (11)
    • Software (3)
      • Design Pattern (3)
    • Computer Science (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Postman
  • 자바
  • 이펙티브 자바
  • MySQL
  • API
  • APM
  • Java
  • 아이템 23
  • 브루트포스
  • 컴파일설치
  • 가상머신
  • 아이템8
  • 소스설치
  • jwt
  • Spring
  • 아이템9
  • JPA
  • 구현
  • 아이템6
  • 우분투
  • 서버
  • 아이템 25
  • DP
  • node js
  • 파이썬
  • Restful API
  • 에러
  • 수동설치
  • 백준
  • 구동원리

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
nonneng.ee

Daeun-rithm

Algorithm/Dynamic Programming

[Python] 백준 #11052 카드 구매하기

2021. 6. 30. 02:28

11052번: 카드 구매하기 (acmicpc.net)

 

11052번: 카드 구매하기

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

[알고리즘]

DP

 

[접근 방법]

 N개의 카드 팩이 있고, N개의 카드를 구매하는 상황.

 D[i] = 카드 i개를 구매하는 최대 비용, dp[k] = 카드 k개가 들어있는 카드팩의 가격 일 때,

 카드 i개를 구매하는 최대 비용의 경우의 수는

  D[1] + dp[i - 1]

  D[2] + dp[i - 1]

  D[3] + dp[i - 3]

  ...

  D[i] + dp[0]

 

[코드]

1
2
3
4
5
6
7
8
9
10
11
N = int(input())
N_list = list(map(int, input().split()))
N_list = [0] + N_list
dp = [0] * 1001
 
for i in range (N + 1) :
    for j in range(i + 1) :
        # 최대값을 찾기 -> j증가시키기 전 가격( dp[i] ) & j+1된 가격 max로 비교하여 갱신
        # (j+1된 가격 -> N_list[j] + dp[i - j])
        dp[i] = max(dp[i], N_list[j] + dp[i - j])
print(max(dp))
Colored by Color Scripter
cs

 

'Algorithm > Dynamic Programming' 카테고리의 다른 글

[Algorithm/Java] 다이나믹 프로그래밍 복습  (0) 2022.07.14
[Python] 백준 #1932 정수 삼각형  (0) 2021.06.30
[Python] 백준 #1149 RGB거리  (0) 2021.06.30
    'Algorithm/Dynamic Programming' 카테고리의 다른 글
    • [Java] 백준 #1463 1로 만들기
    • [Algorithm/Java] 다이나믹 프로그래밍 복습
    • [Python] 백준 #1932 정수 삼각형
    • [Python] 백준 #1149 RGB거리
    nonneng.ee
    nonneng.ee

    티스토리툴바