강의

멘토링

커뮤니티

인프런 커뮤니티 질문&답변

wndud님의 프로필 이미지
wndud

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

다이나믹 프로그래밍 문제 중에서 질문이 있습니다.

작성

·

302

0

안녕하세요. 선생님~

강의 너무 잘 듣고 있고, 질문에 항상 세심하게 답변해주셔서 감사합니다.

바쁘신 와중에, 이런 질문을 해도 될지 모르겠네요;ㅠ

선생님 강의를 듣고 나름 자신감이 생겨서 백준 알고리즘 사이트에 있는 '평범한 배낭2'문제를 풀어보았는데요..

채점하면 틀렸다고만 나오고.. 잘 풀리지가 않습니다ㅠ 

지나친 부탁같아서 넘기셔서 괜찮습니다!

혹시 시간이 조금 있으시다면, 어떤 부분이 잘 못된건지 확인 부탁드립니다:)

혹은 풀이방법을 알려주시면 감사하겠습니다.

아래 문제 링크와 제가 푼 풀이를 붙여 놓았습니다.

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

[코딩 구현한 그림-예제1]

[예제2]

답변 1

0

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

이 문제는 물건의 개수가 유한개이기 때문에 "최대점수구하기" 처럼 풀어야 합니다.

"최대점수구하기"는 무조건 1개 였기때문에 쉽지만 이 문제는 각 물건마다 개수가 각기 k개로 달라 2중 for문이 아니라 3중 for문 다이나믹입니다. 

하지만 m제한과 k제한이 커 약간의 비트개념까지 넣어야 시간초과를 면할 수 있습니다.

아래 블로그를 참조하세요. 

https://rebro.kr/48

wndud님의 프로필 이미지
wndud

작성한 질문수

질문하기