[복기] 12865번: 평범한 배낭

2023. 11. 21. 14:36·IT/BOJ 문제정리

문제

백준 12865번: 평범한 배낭

알고리즘 분류

  • 다이나믹 프로그래밍
  • 배낭 문제

솔루션

input = sys.stdin.readline

n, k = map(int, input().split())
products = [list(map(int, input().split())) for __ in range(n)]

dp = [[0] * (k + 1) for __ in range(n)]
for i in range(n):
    for j in range(0, k + 1):
        if j >= products[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - products[i][0]] + products[i][1])
        else:
            dp[i][j] = dp[i - 1][j]

print(max(dp[n - 1]))
  • 유명한 배낭 문제
  • 2차원 배열 dp를 만들고, 무게마다 최댓값을 계산해서 저장
  • dp의 최댓값을 출력하면 끝

96% 틀렸습니다.

96%에서 자꾸 틀렸는데 질문 게시판에서 해답을 찾았다.

https://www.acmicpc.net/board/view/114723

  • 입력
    1 5
    1 10
  • 정답
    10

그러나 내 코드는 50을 출력한다. 최근에 추가된 반례라서 96%에서 틀린 모양이다. 위 입력에서 dp = [0, 10, 20, 30, 40, 50] 으로 10이 계속해서 더해지는 형태이다. dp[i-1]이 dp[-1] == dp[0]이 되면서 dp의 i번째 줄을 스스로 참조하는 형태가 되버린 것이다. 그래서 그냥 dp 마지막에 빈 배열을 하나 추가해서 해결했다.

input = sys.stdin.readline

n, k = map(int, input().split())
products = [list(map(int, input().split())) for __ in range(n)]

dp = [[0] * (k + 1) for __ in range(n+1)] # n => n+1
for i in range(n):
    for j in range(0, k + 1):
        if j >= products[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - products[i][0]] + products[i][1])
        else:
            dp[i][j] = dp[i - 1][j]

print(max(dp[n - 1]))

'IT > BOJ 문제정리' 카테고리의 다른 글

[프로그래머스][Python] 두 큐의 합 같게 만들기  (1) 2023.11.14
[프로그래머스][JS] n^2 배열 자르기  (0) 2023.09.19
[프로그래머스][JS] 할인 행사  (0) 2023.09.18
[프로그래머스][JS] N개의 최소공배수  (0) 2023.09.13
[프로그래머스][JS] 피보나치 수  (1) 2023.09.09
'IT/BOJ 문제정리' 카테고리의 다른 글
  • [프로그래머스][Python] 두 큐의 합 같게 만들기
  • [프로그래머스][JS] n^2 배열 자르기
  • [프로그래머스][JS] 할인 행사
  • [프로그래머스][JS] N개의 최소공배수
KimCookieYa
KimCookieYa
무엇이 나를 살아있게 만드는가
  • KimCookieYa
    쿠키의 주저리
    KimCookieYa
  • 전체
    오늘
    어제
    • 분류 전체보기 (572)
      • 혼잣말 (87)
      • TIL (2)
      • 커리어 (24)
        • Sendy (21)
        • 외부활동 기록 (2)
      • 프로젝트 (186)
        • 티스토리 API (5)
        • 코드프레소 체험단 (89)
        • Web3 (3)
        • Pint OS (16)
        • 나만무 (14)
        • 대회 (6)
        • 정글 FE 스터디 (16)
        • MailBadara (12)
        • github.io (1)
        • 인공지능 동아리, AID (5)
        • 졸업과제 (18)
        • OSSCA 2024 (1)
      • 크래프톤 정글 2기 (80)
      • IT (167)
        • 코딩 (4)
        • CS (18)
        • 에러 (5)
        • 블록체인 (23)
        • Front-End (38)
        • 알고리즘&자료구조 정리 (3)
        • 코딩테스트 (3)
        • BOJ 문제정리 (41)
        • WILT (12)
        • ML-Agents (4)
        • 강화학습 (1)
        • Android (0)
        • LLM (2)
      • 전공 (1)
        • 머신러닝 (1)
      • 자기계발 (20)
        • 빡공단X베어유 (2)
        • 독서 (15)
  • 블로그 메뉴

    • 홈
    • 방명록
    • Github
    • Velog
    • 관리
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    자바스크립트
    OS
    니어프로토콜
    글리치해커톤
    RNN
    파이썬
    코드프레소
    Flutter
    JavaScript
    리액트
    나만무
    Pint OS
    머신러닝
    사이드프로젝트
    NEAR Protocol
    크래프톤정글
    알고리즘
    위상정렬
    핀토스
    pintos
    블록체인
    부산대
    해커톤
    react
    numpy
    졸업과제
    docker
    딥러닝
    MailBadara
    프로그래머스
  • hELLO· Designed By정상우.v4.10.3
KimCookieYa
[복기] 12865번: 평범한 배낭
상단으로

티스토리툴바