๐Ÿ“ BOJ - ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญ

๋ฌธ์ œ

BOJ 12865๋ฒˆ : ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญ

์ ‘๊ทผ ๋ฐฉ๋ฒ•

๊ฑฐ์˜ ๋ชจ๋“  ์ปด๊ณต ์ „๊ณต์ƒ๋“ค์ด ์ ˆ๋Œ€๋กœ ๊นŒ๋จน์ง€ ์•Š์„ ๋Œ€ํ‘œ ๋ฌธ์ œ์ด๋‹ค. ์ง€๊ธˆ๊นŒ์ง€ ํ–ˆ๋˜ ๋ฐฉ๋ฒ•์œผ๋กœ ์ด ๋ฌธ์ œ๋ฅผ ์ ‘๊ทผํ•˜๋ฉด ์กฐ๊ธˆ ๋‚ฏ์„ค ์ˆ˜๋„ ์žˆ์ง€๋งŒ ํ•œ ๋ฒˆ ๊ทธ๋Œ€๋กœ ์ ‘๊ทผํ•ด๋ณด์ž!

์„ค๋ช…

๋™์ ๊ณ„ํš๋ฒ• ๋ฌธ์ œ์˜ ์ฒซ ๋ฒˆ์งธ ๋‹จ๊ณ„์ธ ํ˜„์žฌ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๊ณผ๊ฑฐ๋ฅผ ์ถ”์ธก์„ ํ•ด๋ณด์ž. ๋ฌผํ’ˆ์˜ ์ˆ˜๋Š” NN, ์ค€์„œ๊ฐ€ ๋ฒ„ํ‹ธ ์ˆ˜ ์žˆ๋Š” ๋ฌด๊ฒŒ๋ฅผ KK์ด๋‹ค. ๋˜ํ•œ ๋ฌผ๊ฑด์„ ๋ฌด๊ฒŒ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ์ž‘์€ ๊ฒƒ์„ ๊ฐ€์žฅ ๋จผ์ € ๋„ฃ๋Š”๋‹ค๊ณ  ๊ฐ€์ •ํ•œ๋‹ค. ๊ทธ๋Ÿผ ์ด ๋ฌธ์ œ์—์„œ์˜ ํ˜„์žฌ๋Š” ๋ฌด์—‡์ผ๊นŒ? ๋ฐ”๋กœ ๋ฌผ๊ฑด์„ n๊ฐœ, ๋ฌด๊ฒŒ๋Š” k๊นŒ์ง€ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ์ƒํ™ฉ์—์„œ n๋ฒˆ์งธ ๋ฌผ๊ฑด์„ ๋„ฃ์„์ง€ ๋ง์ง€๋ฅผ ๋งํ•œ๋‹ค. (์ด ๋•Œ, nโ‰คNn โ‰ค N์ด๊ณ  kโ‰คKk โ‰ค K์ด๋‹ค.) ๋ฌธ์ œ์˜ ์˜ˆ์‹œ๋ฅผ ๊ฐ€์ง€๊ณ  ์ผ€์ด์Šค๋ฅผ ๋‚˜๋ˆ„์–ด ๋ณด์ž.

๊ฒฝ์šฐ 1. ๋ฌผ๊ฑด์„ ๋„ฃ์„ ์ˆ˜ ์—†์„ ๋•Œ

๋ฌผ๊ฑด 2๊ฐœ, ๋ฌด๊ฒŒ๋Š” 3๋ฅผ ๋“ค ์ˆ˜ ์žˆ๊ณ  ํ˜„์žฌ ๋ฌผ๊ฑด์ด (4, 7)์ผ ๋•Œ, ๋„ฃ์„ ์ˆ˜ ์—†์œผ๋ฏ€๋กœ ๋ฌผ๊ฑด 1๊ฐœ, ๋ฌด๊ฒŒ๋Š” 3์ผ ๋•Œ์˜ ์ตœ๋Œ€ ๊ฐ€์น˜ํ•ฉ์ธ 6์ด ํ˜„์žฌ์˜ ์ตœ๋Œ€๊ฐ’์ด ๋œ๋‹ค.

๊ฒฝ์šฐ 2. ๋ฌผ๊ฑด์„ ๋„ฃ์„ ์ˆ˜ ์žˆ์ง€๋งŒ ๊ทธ ์ „์˜ ๊ฐ€์น˜ํ•ฉ์„ ๊ทธ๋Œ€๋กœ ๋”ฐ๋ฅผ ๋•Œ

๋ฌผ๊ฑด์„ 3๊ฐœ, ๋ฌด๊ฒŒ๋Š” 7๋ฅผ ๋“ค ์ˆ˜ ์žˆ๊ณ  ํ˜„์žฌ ๋ฌผ๊ฑด์ด (5, 12)์ผ ๋•Œ, ๋„ฃ์„ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ํ˜„์žฌ ๋ฌผ๊ฑด์„ ๋„ฃ์„์ง€ ๋ง์ง€๋ฅผ ๊ฒฐ์ •ํ•ด์•ผ ํ•œ๋‹ค. ๋งŒ์•ฝ ๋„ฃ๋Š”๋‹ค๊ณ  ํ•˜๋ฉด, ํ˜„์žฌ ๊ฐ€๋Šฅํ•œ ๋ฌด๊ฒŒ์ธ 7์—์„œ 5๋ฅผ ๋บ€ ๋ฌด๊ฒŒ๊ฐ€ 2์ด๊ณ , ๋ฌผ๊ฑด์€ 2๊ฐœ๊นŒ์ง€ ๊ฐ€๋Šฅํ•  ๋•Œ์˜ ๊ฐ€์น˜ํ•ฉ์ธ 0์— ํ˜„์žฌ ๊ฐ€์น˜์ธ 12์„ ๋”ํ•œ 12๊ฐ€ ๋œ๋‹ค. ๋งŒ์•ฝ ๋„ฃ์ง€ ์•Š๋Š”๋‹ค๋ฉด, ๋ฐ”๋กœ ์ „ ๋ฌด๊ฒŒ๊ฐ€ 7์ด๊ณ , ๋ฌผ๊ฑด์€ 2๊ฐœ๊นŒ์ง€ ๊ฐ€๋Šฅํ•  ๋•Œ์˜ ๊ฐ€์น˜ํ•ฉ์ธ 14๊ฐ€ ๋œ๋‹ค. ๋‘˜ ์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ€์น˜ํ•ฉ์ธ 14๊ฐ€ ํ˜„์žฌ์˜ ์ตœ๋Œ€ ๊ฐ€์น˜ํ•ฉ์ด ๋œ๋‹ค.

๊ฒฝ์šฐ 3. ๋ฌผ๊ฑด์„ ๋„ฃ์„ ์ˆ˜ ์žˆ์ง€๋งŒ ๊ฐ€์น˜ํ•ฉ์„ ๊ฐฑ์‹ ํ•  ๋•Œ

๋ฌผ๊ฑด 2๊ฐœ, ๋ฌด๊ฒŒ๋Š” 7์„ ๋“ค ์ˆ˜ ์žˆ๊ณ  ํ˜„์žฌ ๋ฌผ๊ฑด์ด (4, 7)์ผ ๋•Œ, ๋„ฃ์„ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ํ˜„์žฌ ๋ฌผ๊ฑด์„ ๋„ฃ์„์ง€ ๋ง์ง€๋ฅผ ๊ฒฐ์ •ํ•ด์•ผ ํ•œ๋‹ค. ๋งŒ์•ฝ ๋„ฃ๋Š”๋‹ค๊ณ  ํ•˜๋ฉด, ํ˜„์žฌ ๊ฐ€๋Šฅํ•œ ๋ฌด๊ฒŒ์—์„œ 4๋ฅผ ๋บ€ ๋ฌด๊ฒŒ๊ฐ€ 3์ด๊ณ  ์†Œ์ง€ ๊ฐ€๋Šฅํ•œ ๋ฌผ๊ฑด์ด 1๊ฐœ์ผ ๋•Œ์˜ ๊ฐ€์น˜ํ•ฉ์ธ 6์— ํ˜„์žฌ ๋ฌผ๊ฑด์˜ ๊ฐ€์น˜์ธ 7์„ ๋”ํ•œ ๊ฐ€์น˜ํ•ฉ 14๊ฐ€ ๋œ๋‹ค. ๋งŒ์•ฝ ๋„ฃ์ง€ ์•Š๋Š”๋‹ค๋ฉด, ๋ฌผ๊ฑด 1๊ฐœ, ๋ฌด๊ฒŒ๋Š” 7์„ ๋“ค ์ˆ˜ ์žˆ์„ ๋•Œ์˜ ๊ฐ€์น˜ํ•ฉ์ธ 6์ด ๋œ๋‹ค. ๋‘˜ ์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ€์น˜ํ•ฉ์ธ 14๊ฐ€ ํ˜„์žฌ์˜ ์ตœ๋Œ€ ๊ฐ€์น˜ํ•ฉ์ด ๋œ๋‹ค.

๊ฒฐ๋ก 

๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํ…Œ์ด๋ธ”๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ii๋Š” ํ˜„์žฌ ์†Œ์ง€ ๊ฐ€๋Šฅํ•œ ๋ฌผ๊ฑด์˜ ๊ฐœ์ˆ˜์ด๊ณ  jj๋Š” ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ฌด๊ฒŒ์ด๋‹ค. ๊ฐ ์นธ์€ ์†Œ์ง€ ๊ฐ€๋Šฅํ•œ ๋ฌผ๊ฑด์˜ ๊ฐœ์ˆ˜๊ฐ€ ii์ด๊ณ  ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ฌด๊ฒŒ๊ฐ€ jj์ผ ๋•Œ์˜ ์ตœ๋Œ€ ๊ฐ€์น˜ํ•ฉ์ด๋‹ค.

knapsack


์ •๋ฆฌํ•˜๋ฉด ์ œ์•ฝ์‚ฌํ•ญ์ธ ๋ฌด๊ฒŒ์™€ ๋ฌผ๊ฑด์˜ ๊ฐœ์ˆ˜์— ๋”ฐ๋ผ ์ตœ๋Œ€ ๊ฐ€์น˜ํ•ฉ์„ ๊ฐฑ์‹ ํ•˜๋ฉด ๋œ๋‹ค. ์ฆ‰, ํ˜„์žฌ์˜ ์ƒํ™ฉ์—์„œ ๊ณผ๊ฑฐ์˜ ์ƒํ™ฉ์—์„œ ํ˜„์žฌ ๋ฌผ๊ฑด์„ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š”์ง€ ์—†๋Š”์ง€ ํŒ๋‹จํ•œ๋‹ค. ๋„ฃ์„ ์ˆ˜ ์—†๋‹ค๋ฉด ๋ฐ”๋กœ ๊ทธ ์ „์˜ ์ตœ๋Œ€ ๊ฐ€์น˜ํ•ฉ์„ ๊ฐ€์ ธ์˜ค๊ณ , ๋„ฃ์„ ์ˆ˜ ์žˆ๋‹ค๋ฉด ํ˜„์žฌ์˜ ๋ฌผ๊ฑด์„ ๋„ฃ์„ ๋•Œ์™€ ๋„ฃ์ง€ ์•Š์„ ๋•Œ์˜ ๊ฐ€์น˜ ์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ’์œผ๋กœ ๊ฐฑ์‹ ํ•ด๋‚˜๊ฐ€๋ฉด ๋œ๋‹ค.

์ด๋ฅผ ์ ํ™”์‹์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

table[i][j]=max(table[iโˆ’1][jโˆ’w]+v,table[iโˆ’1][j])table[i][j] = max(table[i-1][j-w]+v, table[i-1][j])
  • table[i][j]table[i][j] : ์†Œ์ง€ ๊ฐ€๋Šฅํ•œ ๋ฌผ๊ฑด์˜ ๊ฐœ์ˆ˜๊ฐ€ ii๊ฐœ์ด๊ณ  ๋ฌด๊ฒŒ๋Š” jj์ผ ๋•Œ์˜ ์ตœ๋Œ€ ๊ฐ€์น˜ํ•ฉ
  • ww, vv : ํ˜„์žฌ ๋„ฃ์œผ๋ ค๋Š” ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ, ๊ฐ€์น˜

๊ตํ›ˆ

๋™์ ๊ณ„ํš๋ฒ• ๋ฌธ์ œ๋ฅผ ํ’€๊ณ  ๋‚ด๋ฆฐ ๊ฒฐ๋ก ์€ ํ…Œ์ด๋ธ”์„ ์ž˜ ๋งŒ๋“œ๋Š” ๊ฒƒ์ด๋‹ค. ํ…Œ์ด๋ธ”์˜ ์—ด ํ˜น์€ ํ–‰์€ ์ œ์•ฝ์‚ฌํ•ญ(ex. ๋ฌด๊ฒŒ, ๊ฐœ์ˆ˜ ๋“ฑ)์ด ๋˜๊ณ  ์ œ์•ฝ์‚ฌํ•ญ์„ ํ•˜๋‚˜์”ฉ ํ’€๋ฉด์„œ ํ…Œ์ด๋ธ” ์•ˆ์˜ ๊ฐ’์„ ๊ฐฑ์‹ ํ•œ๋‹ค. ํ…Œ์ด๋ธ” ์•ˆ์˜ ๊ฐ’์€ ๋ฌธ์ œ์—์„œ ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š” ์ถœ๋ ฅ๊ฐ’์ด๋‹ค.

์†Œ์Šค ์ฝ”๋“œ

from collections import namedtuple

# ์ž…๋ ฅ
n, k = map(int, input().split())
Stuff = namedtuple('Stuff', 'weight value')
lst = [Stuff(0, 0)]
for _ in range(n):
    w, v = map(int, input().split())
    stuff = Stuff(weight=w, value=v)
    lst.append(stuff)
lst.sort()


# ํ…Œ์ด๋ธ” ์ฑ„์šฐ๊ธฐ
table = [[0]*(k+1) for _ in range(n+1)]
for i in range(1, n+1):
    # ํ˜„์žฌ ๋„ฃ์œผ๋ ค ํ•˜๋Š” ๋ฌผ๊ฑด์˜ ๋ฌด๊ฒŒ์™€ ๊ฐ€์น˜
    w, v = lst[i].weight, lst[i].value
    for j in range(1, k+1):
        # ํ˜„์žฌ ๊ฐ€๋Šฅํ•œ ๋ฌด๊ฒŒ j๋ณด๋‹ค ๋ฌด๊ฒŒ๊ฐ€ ์ž‘์„ ๋•Œ = ๋„ฃ์„ ์ˆ˜ ์žˆ์Œ
        if w <= j:
            # ๋‘ ์ผ€์ด์Šค ๋น„๊ต
            # 1. i-1๊ฐœ, j-w๋งŒํผ ๋„ฃ์„ ์ˆ˜ ์žˆ์„ ๋•Œ์˜ ๊ฐ€์น˜ํ•ฉ + ํ˜„์žฌ ๋ฌผ๊ฑด์˜ ๊ฐ€์น˜
            # 2. i-1๊ฐœ, j๋งŒํผ ๋„ฃ์„ ์ˆ˜ ์žˆ์„ ๋•Œ์˜ ๊ฐ€์น˜ํ•ฉ
            if v + table[i-1][j-w] > table[i-1][j]:
                # ์ผ€์ด์Šค 1. ๊ฐฑ์‹ 
                table[i][j] = v + table[i-1][j-w]
            else:
                # ์ผ€์ด์Šค 2. ๊ทธ๋Œ€๋กœ
                table[i][j] = table[i-1][j]
        # ํ˜„์žฌ ๊ฐ€๋Šฅํ•œ ๋ฌด๊ฒŒ j๋ณด๋‹ค ๋ฌด๊ฒŒ๊ฐ€ ํด ๋•Œ = ๋ชป ๋„ฃ์Œ
        # ๊ทธ ์ „์˜ ๊ฐ€์น˜ํ•ฉ์˜ ์ตœ๋Œ€๊ฐ’์„ ๊ทธ๋Œ€๋กœ ๊ฐ€์ ธ์˜ด
        else:
            table[i][j] = table[i-1][j]

print(table[n][k])

Written by@์ฝ”๋”ฉํ•˜๋Š”ํŽญ๊ท„
ํŒŒ์ด์ฌ๊ณผ ์›น์— ๊ด€์‹ฌ ๋งŽ์€ ์ปด๊ณต ์ „๊ณต์ž๐Ÿ‘ฉโ€๐Ÿ’ป

GitHubInstagram