문제 링크: www.acmicpc.net/problem/12865
유명한 dp문제인 knapsack 문제입니다. 굳이 2차원 배열을 사용하지 않아도 1차원 리스트로 덮어 쓰면 풀이가 가능합니다.
이 문제는 각 물건을 1번씩 밖에 사용하지 못하므로 1차원 리스트로 풀이할 경우 거꾸로 탐색하면서 풀어야 각 물건을 1번씩만 사용하게 됩니다. 왜 거꾸로 해야하는지는 한번 생각해보시길 바랍니다.
'알고리즘' 카테고리의 다른 글
| 백준 게임개발 (Python/Go) (0) | 2021.04.04 |
|---|---|
| 백준 최단경로 (Python/Go) (0) | 2021.04.03 |
| 백준 피자굽기 (Python/Go) (1) | 2021.04.02 |
| 백준 가장 긴 증가하는 부분 수열4 (Python/Go) (0) | 2021.04.01 |
| 백준 욕심쟁이판다 (Python/Go) (0) | 2021.03.31 |
