땅지원
땅지원's Personal blog
땅지원
전체 방문자
오늘
어제
  • 전체 (353)
    • Frontend (2)
      • React (2)
    • Backend (90)
      • Java (16)
      • Python (19)
      • Spring (23)
      • Database (21)
      • Troubleshooting (8)
    • DevOps (27)
      • ELK (13)
    • CS (40)
    • OS (2)
      • Linux (2)
    • Algorithm (95)
      • concept (18)
      • Algorithm Problem (77)
    • 인공지능 (25)
      • 인공지능 (12)
      • 연구노트 (13)
    • 수업정리 (35)
      • 임베디드 시스템 (10)
      • 데이터통신 (17)
      • Linux (8)
    • 한국정보통신학회 (5)
      • 학술대회 (4)
      • 논문지 (1)
    • 수상기록 (8)
      • 수상기록 (6)
      • 특허 (2)
    • 삼성 청년 SW 아카데미 (6)
    • 42seoul (12)
    • Toy project (3)
    • 땅's 낙서장 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 20.11.6 BB21플러스 온라인 학술대회
  • 20.10.30 한국정보통신학회 온라인 학술대회

인기 글

태그

  • D
  • ㅗ
  • I
  • 이것이 리눅스다 with Rocky Linux9
  • E

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
땅지원
Algorithm/Algorithm Problem

백준 11052 카드 구매하기

Algorithm/Algorithm Problem

백준 11052 카드 구매하기

2021. 10. 29. 18:20

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

 

11052번: 카드 구매하기

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

www.acmicpc.net

 

n = int(input())
dp = [0] * (n+1)
data = [0] + list(map(int,input().split()))
dp[1] = data[1]

for i in range(2,n+1):
    for j in range(1,i+1):
        if dp[i] < dp[i-j] + data[j]:
            dp[i] = dp[i - j] + data[j]

print(dp[n])

DP, 다이나믹 프로그래밍 문제 이기 때문에  리스트를 먼저 선언한다.

편리함을 위해 index 0은 0으로 초기화 하고 시작하자.

dp[1]은 data[1]와 동일하다. why) 카드 1개를 뽑는 최댓값은 1개의 값이기 때문!

 

카드를 3개 이상사는것부터 최댓값을 구하려면 모든 경우를 고려해야하지만 최댓값을 구하는것이기 때문에

n개를 산다하면 

 

dp[2] = dp[1] + data[1]  # 1장 + 1장

           dp[0] + data[2]  # 2장짜리 1개 사는 경우

 

dp[3] = dp[2] + data[1]  # 2장 최댓값 + 1장

           dp[1] + data[2]  #1장 최댓값 + 2장

           dp[0] + data[3]  #3장짜리 1개 사는 경우

 

dp[4] = dp[3] + data[1] # 3장 최댓값 + 1장

           dp[2] + data[2] # 2장 최댓값  + 2장 

           dp[1] +data[3]  # 1장 최댓값 + 3장

           dp[0] + data[4] # 4장짜리 1개 사는 경우

 

 

이렇게 순서쌍을 두고 최댓값을 찾는식으로 풀면 해결 가능

 

'Algorithm > Algorithm Problem' 카테고리의 다른 글

백준 6064 카잉 달력  (0) 2021.11.04
백준 17427 약수의 합2  (0) 2021.11.02
##백준 15990 1, 2, 3 더하기5  (0) 2021.10.29
백준 1406 에디터  (0) 2021.10.19
백준 1018 체스판 다시 칠하기  (0) 2021.10.13
    'Algorithm/Algorithm Problem' 카테고리의 다른 글
    • 백준 17427 약수의 합2
    • ##백준 15990 1, 2, 3 더하기5
    • 백준 1406 에디터
    • 백준 1018 체스판 다시 칠하기
    땅지원
    땅지원
    신입 개발자의 우당탕탕 기술 블로그

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.