MCP๋กœ ์—ฐ๊ฒฐ โ†’

๊ณ„์‚ฐ ์ž…๋ ฅ

ํ‘œ์ค€ ์„ธํŠธ: 45, 35, 25, 10, 5, 2.5

๊ณต์‹

๊ด‘๊ณ 

๊ฒฐ๊ณผ

ํ•œ์ชฝ๋‹น ๋ฌด๊ฒŒ
90
์–‘์ชฝ์— ๊ฐ๊ฐ ๋ผ์šธ ์›ํŒ ๋ฌด๊ฒŒ (lb)
ํ•œ์ชฝ ์›ํŒ ๊ตฌ์„ฑ 2 ร— 45 lb
์ „์ฒด ์„ธํŒ… ๋ฌด๊ฒŒ 225 lb
๋งž์ถœ ์ˆ˜ ์—†๋Š” ๋ฌด๊ฒŒ (์›ํŒ์œผ๋กœ ์ฑ„์šธ ์ˆ˜ ์—†์Œ) 0 lb

๋ฐ”๋ฒจ ์›ํŒ ๊ณ„์‚ฐ๊ธฐ๋ž€?

์ด ๋„๊ตฌ๋Š” ๋ชฉํ‘œ ์ค‘๋Ÿ‰์„ ๋งž์ถ”๊ธฐ ์œ„ํ•ด ๋ฐ”๋ฒจ ์–‘์ชฝ์— ์–ด๋–ค ์›ํŒ์„ ๋ผ์›Œ์•ผ ํ•˜๋Š”์ง€ ์ •ํ™•ํ•˜๊ฒŒ ์•Œ๋ ค์ค๋‹ˆ๋‹ค. ๋ฐ”์— ์›ํŒ์„ ๋‹ค๋Š” ์ผ์€ ์šด๋™ํ•  ๋•Œ๋งˆ๋‹ค ์ˆ˜์‹ญ ๋ฒˆ์”ฉ ๋ฐ˜๋ณตํ•˜๋Š” ์ž‘์€ ๊ณ„์‚ฐ ๋ฌธ์ œ์ธ๋ฐ, ์ด ๊ณ„์‚ฐ๊ธฐ๋Š” ๊ทธ ๊ณ„์‚ฐ์„ ์ฆ‰์‹œ ํ•ด๊ฒฐํ•ด ์ค๋‹ˆ๋‹ค. ํŠนํžˆ ๋ฌด๊ฑฐ์šด ์„ธํŠธ ์‚ฌ์ด์— ์ง€์ณ ๋จธ๋ฆฌ๊ฐ€ ์ž˜ ์•ˆ ๋Œ์•„๊ฐˆ ๋•Œ ์–ด๋ฆผ์ง์ž‘ ์—†์ด ๋”ฑ ๋งž๊ฒŒ ์„ธํŒ…ํ•  ์ˆ˜ ์žˆ์ฃ . ์ฐธ๊ณ ๋กœ ์ด ๊ณ„์‚ฐ๊ธฐ๋Š” lb(ํŒŒ์šด๋“œ) ๋‹จ์œ„ ์›ํŒ์„ ๊ธฐ์ค€์œผ๋กœ ํ•˜๋ฉฐ, ๋ฏธ๊ตญ์‹ ํ—ฌ์Šค์žฅ์—์„œ ํ”ํžˆ ์“ฐ๋Š” ๊ทœ๊ฒฉ์ž…๋‹ˆ๋‹ค.

์ค‘์•™ ๋ฐ” ์–‘์ชฝ์— ๋Œ€์นญ์œผ๋กœ ์›ํŒ์„ ์Œ“์€ ๋กœ๋“œ๋œ ๋ฐ”๋ฒจ
์ค‘์•™ ๋ฐ” ์–‘์ชฝ์— ๊ฐ™์€ ์›ํŒ์„ ๋ผ์šด ํ‘œ์ค€ ๋ฐ”๋ฒจ.

์‚ฌ์šฉ ๋ฐฉ๋ฒ•

๋ชฉํ‘œ ์ค‘๋Ÿ‰(์›ํŒ์„ ๋ชจ๋‘ ๋ผ์šด ๋ฐ”๋ฒจ ์ „์ฒด ๋ฌด๊ฒŒ)๊ณผ ๋ฐ” ๋ฌด๊ฒŒ๋ฅผ ์ž…๋ ฅํ•˜์„ธ์š”. ์˜ฌ๋ฆผํ”ฝ ๋ฐ”๋ฒจ์€ ๋ณดํ†ต 45 lb์ด๊ณ , ์—ฌ์„ฑ์šฉ ๋ฐ”๋Š” 35 lb์ธ ๊ฒฝ์šฐ๊ฐ€ ๋งŽ์Šต๋‹ˆ๋‹ค. ๊ณ„์‚ฐ๊ธฐ๋Š” ๋จผ์ € ๋ฐ” ๋ฌด๊ฒŒ๋ฅผ ๋นผ๊ณ  ๋‚จ์€ ๋ฌด๊ฒŒ๋ฅผ ์–‘์ชฝ์œผ๋กœ ๋˜‘๊ฐ™์ด ๋‚˜๋ˆˆ ๋’ค, ํ‘œ์ค€ ์›ํŒ ์„ธํŠธ(45, 35, 25, 10, 5, 2.5 lb)๋ฅผ ์‚ฌ์šฉํ•ด ํ•œ์ชฝ์— ๋ผ์šธ ์›ํŒ ๊ตฌ์„ฑ์„ ๋ณด์—ฌ์ค๋‹ˆ๋‹ค.

๊ณ„์‚ฐ ๊ณต์‹ ์„ค๋ช…

๋จผ์ € ํ•œ์ชฝ ๋ฌด๊ฒŒ๋ฅผ ๊ตฌํ•ฉ๋‹ˆ๋‹ค:

$$\text{per side} = \frac{\text{target} - \text{bar}}{2}$$

๊ทธ๋‹ค์Œ ํƒ์š•(greedy) ๋ฐฉ์‹์œผ๋กœ ๊ฐ€์žฅ ํฐ ์›ํŒ๋ถ€ํ„ฐ ์ฑ„์›Œ ๋„ฃ์Šต๋‹ˆ๋‹ค. ๊ฐ ์›ํŒ ํฌ๊ธฐ๋งˆ๋‹ค ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋งŒํผ ์ตœ๋Œ€๋กœ ๋ผ์šฐ๊ณ , ๊ทธ ๋ฌด๊ฒŒ๋ฅผ ๋บ€ ๋’ค ๋” ์ž‘์€ ์›ํŒ์œผ๋กœ ๋„˜์–ด๊ฐ‘๋‹ˆ๋‹ค:

$$n_i = \left\lfloor \frac{r}{d_i} \right\rfloor,\quad r \leftarrow r - n_i d_i$$

์–ด๋–ค ์›ํŒ์œผ๋กœ๋„ ์ฑ„์šธ ์ˆ˜ ์—†๋Š” ์žํˆฌ๋ฆฌ ๋ฌด๊ฒŒ๋Š” "๋งž์ถœ ์ˆ˜ ์—†๋Š” ๋ฌด๊ฒŒ"๋กœ ํ‘œ์‹œ๋˜๋Š”๋ฐ, ์ด๋Š” ํ˜„์žฌ ์›ํŒ์œผ๋กœ๋Š” ๋ชฉํ‘œ ์ค‘๋Ÿ‰์— ์ •ํ™•ํžˆ ๋„๋‹ฌํ•  ์ˆ˜ ์—†๋‹ค๋Š” ์‹ ํ˜ธ์ž…๋‹ˆ๋‹ค(5 lb ๋‹จ์œ„๋กœ ๋งž์ถฐ ๋ณด์„ธ์š”).

์ด ๋ชฉํ‘œ ๋ฌด๊ฒŒ๋ฅผ ๋ฐ”์™€ ์–‘์ชฝ ๋™์ผํ•œ ๋‘ ์›ํŒ ๋”๋ฏธ๋กœ ๋‚˜๋ˆˆ ๋„์‹
์ด ๋ชฉํ‘œ = ๋ฐ” ๋ฌด๊ฒŒ + ์–‘์ชฝ ๋™์ผ: (๋ชฉํ‘œ โˆ’ ๋ฐ”)๋ฅผ 2๋กœ ๋‚˜๋ˆˆ ๊ฐ’์ด ํ•œ์ชฝ ๋ฌด๊ฒŒ.

์‹ค์ œ ์˜ˆ์‹œ

45 lb ๋ฐ”์— ๋ชฉํ‘œ 225 lb์ธ ๊ฒฝ์šฐ: \((225 - 45) \div 2 = 90\) lb๋กœ ํ•œ์ชฝ๋‹น 90 lb. ํƒ์š• ๋ฐฉ์‹์œผ๋กœ ์ฑ„์šฐ๋ฉด ํ•œ์ชฝ์— \(45 \text{ lb} \times 2 = 90\) lb๋กœ ๋”ฑ ๋งž์•„๋–จ์–ด์ง‘๋‹ˆ๋‹ค. ์ „์ฒด ๋ฌด๊ฒŒ๋Š” \(45 + 90 \times 2 = 225\) lb๋กœ, ์–‘์ชฝ์— ์›ํŒ ๋‘ ์žฅ์”ฉ ๋ผ์šฐ๋Š” ๊ทธ ์œ ๋ช…ํ•œ ๊ธฐ์ค€ ๋ฌด๊ฒŒ์ž…๋‹ˆ๋‹ค.

์ž์ฃผ ๋ฌป๋Š” ์งˆ๋ฌธ

"๋งž์ถœ ์ˆ˜ ์—†๋Š” ๋ฌด๊ฒŒ"๋Š” ์™œ ๋‚˜์˜ค๋‚˜์š”? ๋ชฉํ‘œ ์ค‘๋Ÿ‰์—์„œ ๋ฐ” ๋ฌด๊ฒŒ๋ฅผ ๋บ€ ๊ฐ’์ด ๊ฐ€์ง„ ์›ํŒ์œผ๋กœ ๋‚˜๋ˆ„์–ด๋–จ์–ด์ง€์ง€ ์•Š์œผ๋ฉด(์˜ˆ: ์–ด์ค‘๊ฐ„ํ•œ 0.5 lb ๋‹จ์œ„), ๋‚จ๋Š” ๋ฌด๊ฒŒ๊ฐ€ ์—ฌ๊ธฐ์— ํ‘œ์‹œ๋ฉ๋‹ˆ๋‹ค. ์ฆ‰ ๊ทธ ์ •ํ™•ํ•œ ๋ฌด๊ฒŒ๋Š” ๋ผ์šธ ์ˆ˜ ์—†๋‹ค๋Š” ๋œป์ž…๋‹ˆ๋‹ค.

๋ฐ” ๋ฌด๊ฒŒ๋Š” ์–ผ๋งˆ๋กœ ์„ค์ •ํ•ด์•ผ ํ•˜๋‚˜์š”? ํ‘œ์ค€ ์˜ฌ๋ฆผํ”ฝ ๋ฐ”๋Š” 45 lb์ž…๋‹ˆ๋‹ค. ์—ฌ์„ฑ์šฉ ๋ฐ”๋Š” 35 lb, ํ…Œํฌ๋‹‰ ๋ฐ”๋Š” 15 lb๋ฅผ ์‚ฌ์šฉํ•˜๊ณ , ๋ฐ” ๋ฌด๊ฒŒ๋ฅผ ๋ฌด์‹œํ•˜๋ ค๋ฉด 0์„ ์ž…๋ ฅํ•˜์„ธ์š”.

ํ‚ฌ๋กœ๊ทธ๋žจ(kg)๋„ ์ง€์›ํ•˜๋‚˜์š”? ์—ฌ๊ธฐ ์›ํŒ ์„ธํŠธ๋Š” ํŒŒ์šด๋“œ(lb) ๋‹จ์œ„์ž…๋‹ˆ๋‹ค. ์ •ํ™•ํ•œ ์›ํŒ ์ถ”์ฒœ์„ ๋ฐ›์œผ๋ ค๋ฉด ํŒŒ์šด๋“œ ๊ฐ’์œผ๋กœ ์ž…๋ ฅํ•˜์„ธ์š”.

์ตœ์ข… ์—…๋ฐ์ดํŠธ: