의식이 흐르는대로 해보는 프로그래밍

목차 접근 배낭(Knapsack) 알고리즘 문제다. 배낭 알고리즘에 대해선 자세히 써놓았던 이전 아티클을 참고해보자. 2023.12.11 - [알고리즘(Algorithm)] - [BOJ] 12865번 : 평범한 배낭(DP, Knapsack) 해결 배낭 알고리즘은 대표적인 DP 문제로 축의 의미를 어떻게 정의할건지가 중요하다. 당연히 한 축은 탐새할 물건의 인덱스가 되어야 할 것이다. 나머지 한 축은 가치를 저장할 시점의 용량이 되어야하는데, 여기선 두 가지가 있다. 하나는 사용 중인 메모리 바이트 수(`M`) 다른 하나는 비활성화 했을 때의 비용(`C`) 다. 하지만 메모리 바이트 수를 축으로 삼자니 범위가 $ 1 \le M \le 10,000,000 $ 로 말이 안된다. 그럼으로 비활성화 했을 때의 비..

접근 문제 그대로 평범한 배낭 문제다. D.P.를 이용한 Knasack알고리즘을 사용해서 해결할 수 있다. (여담이지만, 올리고 있는 글순서를 보면 알겠지만 솔브닥 클래스 클리어중인데, 이 문제 2년전쯤 그리디 공부할 때 시도했다가 틀리고 안풀고있었던걸 이제 알았다.) (여담2이지만, 이번에 풀 때도 1초틀이었는데, 2년전에 시도했던 코드랑 구조가 똑같았다. 난 발전이 없는것인가...? 하지만 이번엔 해결했다. 내가 틀린 반례도 적어두겠다.) 해결 Knapsack 알고리즘을 사용하지 않고, 전체 탐색으로 해결 자체는 가능하다. 당연히 시간초과가 나겠지만. 그러니까 배낭문제는 그냥 배낭으로 풀자.. 변수는 아래와 같다. $ N $ : 물건의 갯수 $ K $ : 버틸 수 있는 최대 무게 dp Table은 $..