๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
CS/์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ฐฑ์ค€ 12865 ํŒŒ์ด์ฌ - ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญ - ๋™์  ๊ณ„ํš๋ฒ•

by ๐ŸŒปโ™š 2021. 10. 21.

๋ฐฑ์ค€ 12865 ํŒŒ์ด์ฌ

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

์ด๋ฒˆ ๋ฌธ์ œ๋Š” ๊ฐ€๋ฐฉ์— ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋ฌด๊ฒŒ๊ฐ€ ์ •ํ•ด์ ธ ์žˆ์„ ๋•Œ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ๋ฌผ๊ฑด์˜ ์ตœ๋Œ€ ๊ฐ€์น˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ผ๋‹จ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ€์žฅ ๋จผ์ € ๋™์  ๊ณ„ํš๋ฒ•์ด ๋– ์˜ฌ๋ž์Šต๋‹ˆ๋‹ค. ๋ฉ”๋ชจ์ด์ œ์ด์…˜์œผ๋กœ ์‚ฌ์šฉํ•  ๊ฐ’์„ ๊ฐ€๋ฐฉ์— ๋“ค์–ด๊ฐ€๋Š” ๋ฌด๊ฒŒ๋ฅผ ์ค‘์ ์œผ๋กœ ๋‘๊ณ  ๋ฌผ๊ฑด์„ ํ™•์ธํ•  ๋•Œ ๊ฐ€๋ฐฉ์˜ ์ตœ๋Œ€ ๋ฌด๊ฒŒ๋ถ€ํ„ฐ ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ๊นŒ์ง€ ๋ˆ„์ ์‹œํ‚ค๋Š” ๋ฐฉ๋ฒ•์ด ๊ฐ€์žฅ ๋จผ์ € ๋– ์˜ฌ๋ž๋‹ค.

 

 

Python ํ’€์ด 1

import sys
read = sys.stdin.readline

N, K = map(int, read().split())
cache = [0] * (K+1)

for _ in range(N):
    w, v = map(int, read().split())
    for j in range(K, w-1, -1):
        cache[j] = max(cache[j], cache[j-w] + v)
print(cache[-1])

๊ฐ€๋ฐฉ ๋ฌด๊ฒŒ์˜ ์ตœ๋Œ€ ๊ฐ’ K ๋ถ€ํ„ฐ ์—ญ์ˆœ์œผ๋กœ ๋“ค์–ด๊ฐˆ ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ w๊นŒ์ง€ ์ˆœํšŒํ•˜๋ฉด์„œ ํ•ด๋‹น ์œ„์น˜์˜ ์ตœ๋Œ€ ๊ฐ€์น˜(cache[j])์™€ ๋“ค์–ด๊ฐˆ ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ w ๋งŒํผ ์ด์ „์˜ ์ตœ๋Œ€ ๊ฐ€์น˜(cache[j-w])์— ๋ฌผ๊ฑด์˜ ๊ฐ€์น˜ v๋ฅผ ๋”ํ•œ ๊ฐ’ ์ค‘ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•œ๋‹ค.

 

 4๊ฐ€์ง€ ๋ฌผ๊ฑด์„ ์ˆœ์ฐจ์ ์œผ๋กœ ๋„ฃ๋Š”๋‹ค๊ณ  ํ–ˆ์„ ๋•Œ ์บ์‹œ๊ฐ’์˜ ํ๋ฆ„์€ ์œ„์™€ ๊ฐ™์ด ์ง„ํ–‰๋œ๋‹ค. ๊ฐ€๋ฐฉ์— ๋ฌผ๊ฑด์„ ๋„ฃ๋Š”๊ฑฐ๋‹ˆ๊นŒ... ๋ฌผ๊ฑด์ด ๋“ค์–ด๊ฐ„ ์ƒํƒœ์˜ ๋ฌด๊ฒŒ๊ฐ€ ๋ˆ„์ ๋œ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๋ฉด ์‰ฝ๊ฒŒ ์ดํ•ดํ•  ์ˆ˜ ์žˆ๋‹ค.

 

ํ•˜์ง€๋งŒ ์œ„ ๋ฐฉ๋ฒ•์€ ๋ฌผ๊ฑด์˜ ์ˆ˜์™€ ์ƒ๊ด€์—†์ด ์ตœ๋Œ€ ๋ฌด๊ฒŒ K์—์„œ ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ๊นŒ์ง€ ๋งค๋ฒˆ ์ˆœํšŒํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๊ผญ ํ•„์š”ํ•˜์ง€ ์•Š๋Š” ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ ์ƒ๊ธด๋‹ค. ๋งŒ์•ฝ ๋ฌผ๊ฑด๋“ค ๋ฌด๊ฒŒ ํ•ฉ์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜๋งŒ ์ˆœํšŒํ•œ๋‹ค๊ณ ํ•˜๋ฉด ํ›จ์”ฌ ๋น ๋ฅด๊ฒŒ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด๋Ÿฌํ•œ ๊ฒฝ์šฐ ๋ฆฌ์ŠคํŠธ๋ณด๋‹ค๋Š” ๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ๋” ๋น ๋ฅด๊ฒŒ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค.

 

 

Python ํ’€์ด 2

์ด ํ’€์ด๋Š” ๊ฐ€๋ฐฉ ์•ˆ์— ๋“ค์–ด๊ฐ€๋Š” ๋ฌผ๊ฑด๋“ค ๋ฌด๊ฒŒ ํ•ฉ์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•œ ๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.

import sys
read = sys.stdin.readline

N, K = map(int, read().split())
cache = {0: 0}

for _ in range(N):
    curr_w, curr_v = map(int, read().split())
    temp = {}
    for w, v in cache.items():
        if curr_w + w <= K and curr_v + v > cache.get(curr_w + w, 0):
            temp[curr_w + w] = curr_v + v
    cache.update(temp)
print(max(cache.values()))

๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ ํ•œ๊ฐ€์ง€ ์ฃผ์˜ํ•ด์•ผํ•  ๊ฒƒ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ์ˆœํšŒํ•  ๋•Œ ๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ์ˆ˜์ •ํ•˜๋ฉด ์˜ค๋ฅ˜๊ฐ€ ๋ฐœ์ƒํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ์ž„์‹œ๋กœ ์‚ฌ์šฉํ•  ๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ๋งŒ๋“ค์–ด์ฃผ๊ณ  update ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•ด์„œ ๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ์ตœ์‹ ํ™” ํ•ด์ฃผ๋Š” ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•ด์•ผํ•ฉ๋‹ˆ๋‹ค.

 

ํ’€์ด 1๊ณผ ์œ ์‚ฌํ•˜์ง€๋งŒ ๋ฉ”๋ชจ์ด์ œ์ด์…˜ ์บ์‹œ๋กœ ๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•˜๊ณ  ํ˜„์žฌ์˜ ๋ฌผ๊ฑด ๋ฌด๊ฒŒ(curr_w)์™€ ๊ฐ€๋ฐฉ ์•ˆ์˜ ๋ฌผ๊ฑด๋“ค ๋ฌด๊ฒŒ ํ•ฉ(w)์ด ์ตœ๋Œ€ ๊ฐ’ K๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๊ณ  ํ•ด๋‹น ๋ฌด๊ฒŒ ํ•ฉ(curr_w + w)์˜ ๊ฐ€์น˜๊ฐ€ ํ˜„์žฌ ๋ฌผ๊ฑด ๊ฐ€์น˜(curr_v) + ๊ฐ€๋ฐฉ ์•ˆ์˜ ๋ฌผ๊ฑด๋“ค ํ•ฉ์˜ ๊ฐ€์น˜(v) ์ ์€ ๊ฒฝ์šฐ์— ์ž„์‹œ๋กœ ๋งŒ๋“  ๋”•์…”๋„ˆ๋ฆฌ์— ํฌํ•จ ์‹œํ‚จ๋‹ค. ๋งŒ์•ฝ ํ•ด๋‹น ๋ฌผ๊ฑด ํ•ฉ์˜ ๊ฒฝ์šฐ๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ 0๊ณผ ๋”ํ•ด์„œ ํ•ด๋‹น ๋ฌผ๊ฑด๋งŒ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋„๋ก ํ•˜๊ณ  ์ตœ์ข…์ ์œผ๋กœ ๋‹ค ์ˆœํšŒํ•˜๋ฉด cache ๊ฐ’์„ update ํ•ฉ๋‹ˆ๋‹ค.

 

์ตœ์ข…์ ์œผ๋กœ ์ถœ๋ ฅํ•˜๋Š” ๊ฐ’์€ cache์— ๋“ค์–ด ์žˆ๋Š” ๊ฐ’ ์ค‘ ์ตœ๋Œ€๊ฐ’ ์ž…๋‹ˆ๋‹ค.

๋Œ“๊ธ€