인프런 커뮤니티 질문&답변
다이나믹 프로그래밍 문제 중에서 질문이 있습니다.
작성
·
302
0
안녕하세요. 선생님~
강의 너무 잘 듣고 있고, 질문에 항상 세심하게 답변해주셔서 감사합니다.
바쁘신 와중에, 이런 질문을 해도 될지 모르겠네요;ㅠ
선생님 강의를 듣고 나름 자신감이 생겨서 백준 알고리즘 사이트에 있는 '평범한 배낭2'문제를 풀어보았는데요..
채점하면 틀렸다고만 나오고.. 잘 풀리지가 않습니다ㅠ
지나친 부탁같아서 넘기셔서 괜찮습니다!
혹시 시간이 조금 있으시다면, 어떤 부분이 잘 못된건지 확인 부탁드립니다:)
혹은 풀이방법을 알려주시면 감사하겠습니다.
아래 문제 링크와 제가 푼 풀이를 붙여 놓았습니다.
https://www.acmicpc.net/problem/12920
[코딩 구현한 그림-예제1]
[예제2]
답변 1
0
김태원
지식공유자
안녕하세요^^
이 문제는 물건의 개수가 유한개이기 때문에 "최대점수구하기" 처럼 풀어야 합니다.
"최대점수구하기"는 무조건 1개 였기때문에 쉽지만 이 문제는 각 물건마다 개수가 각기 k개로 달라 2중 for문이 아니라 3중 for문 다이나믹입니다.
하지만 m제한과 k제한이 커 약간의 비트개념까지 넣어야 시간초과를 면할 수 있습니다.
아래 블로그를 참조하세요.





