๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ : https://www.acmicpc.net/problem/12865 12865๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ ์ฒซ ์ค์ ๋ฌผํ์ ์ N(1 ≤ N ≤ 100)๊ณผ ์ค์๊ฐ ๋ฒํธ ์ ์๋ ๋ฌด๊ฒ K(1 ≤ K ≤ 100,000)๊ฐ ์ฃผ์ด์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑฐ์ณ ๊ฐ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ W(1 ≤ W ≤ 100,000)์ ํด๋น ๋ฌผ๊ฑด์ ๊ฐ์น V(0 ≤ V ≤ 1,000) www.acmicpc.net ์ด๋ฒ ๋ฌธ์ ๋ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(DP) ๋ฌธ์ ์์ต๋๋ค. ใ๋ฌธ์ ํ์ดใ 1. ๋ฌผ๊ฑด์ ๋ฌด๊ฒ์ ๊ฐ์น๋ฅผ ์์ผ๋ก ๋ฌถ์ด์ ๋ฒกํฐ์ ์ฝ์ 2. ๋ฌผ๊ฑด๋ค์ ๊ฐ์นํฉ์ ๋ด์ ๋ฐฐ์ด dp ์ด๊ธฐํ (1) dp ๋ฐฐ์ด์ ํ์ ๋ฌผ๊ฑด์ ๋ํ๋ด๊ณ (์ฒซ๋ฒ์งธ ๋ฌผ๊ฑด, ๋๋ฒ์งธ ๋ฌผ๊ฑด, ...) ์ด์ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ๋ฅผ ๋ํ๋ (0 ~ K) (2) ์ฒซ๋ฒ์งธ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ..