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

๊ณ„์‚ฐ ์ž…๋ ฅ

๊ณต์‹

๊ด‘๊ณ 

๊ฒฐ๊ณผ

ํ•œ์ชฝ์— ๋ผ์šธ ์›ํŒ
90
lb on each end of the bar
2 ร— 45
ํ•œ์ชฝ์— ๋ผ์šด ์›ํŒ ์ด ๊ฐœ์ˆ˜ 90 lb
๋ฐ”์˜ ์‹ค์ œ ์ด์ค‘๋Ÿ‰ 225 lb
ํ•œ์ชฝ์—์„œ ๋งž์ถ”์ง€ ๋ชปํ•œ ๋‚จ๋Š” ๋ฌด๊ฒŒ 0 lb

์ด ๊ณ„์‚ฐ๊ธฐ๋กœ ํ•  ์ˆ˜ ์žˆ๋Š” ์ผ

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

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

๋จผ์ € ๋‹จ์œ„(lb ๋˜๋Š” kg)๋ฅผ ๊ณ ๋ฅด๊ณ , ๋ชฉํ‘œ ์ด์ค‘๋Ÿ‰์„ ์ž…๋ ฅํ•˜์„ธ์š”(์˜ˆ: 225 lb). ๊ทธ๋‹ค์Œ ๋ฐ” ๋ฌด๊ฒŒ๋ฅผ ์ž…๋ ฅํ•ฉ๋‹ˆ๋‹ค(ํ‘œ์ค€ ์˜ฌ๋ฆผํ”ฝ ๋ฐ”๋Š” 45 lb ๋˜๋Š” 20 kg). ๊ณ„์‚ฐ๊ธฐ๋Š” ์ „์ฒด ๋ฌด๊ฒŒ์—์„œ ๋ฐ” ๋ฌด๊ฒŒ๋ฅผ ๋บ€ ๋’ค ๋‚จ์€ ๋ฌด๊ฒŒ๋ฅผ ์–‘์ชฝ์— ๋˜‘๊ฐ™์ด ๋‚˜๋ˆ„๊ณ , ํ‘œ์ค€ ์›ํŒ ์ค‘์—์„œ ๊ฐ€์žฅ ์ ์€ ๊ฐœ์ˆ˜๋กœ ํ•œ์ชฝ ๋ฌด๊ฒŒ๋ฅผ ๊ตฌ์„ฑํ•ฉ๋‹ˆ๋‹ค.

๊ณ„์‚ฐ ๊ณต์‹ ํ’€์ด

๋จผ์ € ํ•œ์ชฝ์— ๋“ค์–ด๊ฐ€์•ผ ํ•  ๋ฌด๊ฒŒ๋ฅผ ๊ตฌํ•ฉ๋‹ˆ๋‹ค: $$P = \dfrac{\text{๋ชฉํ‘œ ์ค‘๋Ÿ‰} - \text{๋ฐ” ๋ฌด๊ฒŒ}}{2}$$. ๊ทธ๋Ÿฐ ๋‹ค์Œ ํƒ์š•(greedy) ๋ฐฉ์‹์œผ๋กœ ๋ฌด๊ฒŒ๋ฅผ ๋ถ„ํ•ดํ•˜๋Š”๋ฐ, ๋ผ์šธ ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ํฐ ์›ํŒ๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ๊ณจ๋ผ ํ•œ์ชฝ์„ ์ฑ„์›Œ ๋‚˜๊ฐ‘๋‹ˆ๋‹ค. ํŒŒ์šด๋“œ ์›ํŒ์€ \(45, 35, 25, 10, 5, 2.5\) lb๋ฅผ ์‚ฌ์šฉํ•˜๊ณ , ํ‚ฌ๋กœ๊ทธ๋žจ ์›ํŒ์€ \(25, 20, 15, 10, 5, 2.5, 1.25, 0.5\) kg๋ฅผ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค. ๋ณด์œ ํ•œ ์›ํŒ์œผ๋กœ ์ •ํ™•ํžˆ ๋งž์ถœ ์ˆ˜ ์—†๋Š” ๋ฌด๊ฒŒ๋Š” "๋‚จ๋Š” ๋ฌด๊ฒŒ(๋งž์ถ”์ง€ ๋ชปํ•œ ์ฐจ์ด)"๋กœ ํ‘œ์‹œ๋ฉ๋‹ˆ๋‹ค.

์–‘์ชฝ ๋์— ๊ฐ™์€ ๋ฌด๊ฒŒ์˜ ์›ํŒ์„ ๋ผ์šด ๋ฐ”๋ฒจ์˜ ์ธก๋ฉด ๋ชจ์Šต
์›ํŒ์€ ์–‘์ชฝ์— ๋˜‘๊ฐ™์ด ๋‚˜๋ˆ„๋ฏ€๋กœ, ํ•œ์ชฝ์€ (๋ชฉํ‘œ ๋ฌด๊ฒŒ์—์„œ ๋ฐ”๋ฅผ ๋บ€ ๊ฐ’)์„ 2๋กœ ๋‚˜๋ˆˆ ๋งŒํผ์ž…๋‹ˆ๋‹ค.

์˜ˆ์‹œ๋กœ ๋ณด๋Š” ๊ณ„์‚ฐ

45 lb ๋ฐ”์—์„œ ๋ชฉํ‘œ ์ค‘๋Ÿ‰์ด 225 lb์ธ ๊ฒฝ์šฐ: $$\frac{225 - 45}{2} = 90 \text{ lb (ํ•œ์ชฝ์—)}$$ ํƒ์š• ๋ฐฉ์‹์œผ๋กœ ์ฑ„์šฐ๋ฉด \(45 \times 2 = 90\) lb์ด๋ฏ€๋กœ, ์–‘์ชฝ ๋์— ๊ฐ๊ฐ "45 lb ร— 2"๋ฅผ ๋ผ์šฐ๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์‹ค์ œ ์ด์ค‘๋Ÿ‰์€ \(45 + 180 = 225\) lb๋กœ ๋”ฑ ๋งž์•„๋–จ์–ด์ง€๋ฉฐ ๋‚จ๋Š” ๋ฌด๊ฒŒ๋Š” ์—†์Šต๋‹ˆ๋‹ค.

๋ฐ”๋ฒจ ํ•œ์ชฝ ์Šฌ๋ฆฌ๋ธŒ์— ์นผ๋ผ ์ชฝ์œผ๋กœ ํฐ ๊ฒƒ๋ถ€ํ„ฐ ์ž‘์€ ์ˆœ์œผ๋กœ ์›ํŒ์„ ๋ผ์šด ๋ชจ์Šต
๊ฐ€์žฅ ๋ฌด๊ฑฐ์šด ์›ํŒ์„ ๋ฐ”์— ๊ฐ€์žฅ ๊ฐ€๊น๊ฒŒ, ์ ์  ๊ฐ€๋ฒผ์šด ๊ฒƒ์„ ๋ผ์šฐ๊ณ  ๋งˆ์ง€๋ง‰์— ์นผ๋ผ๋กœ ๊ณ ์ •ํ•˜์„ธ์š”.

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

๋ชฉํ‘œ ์ค‘๋Ÿ‰์„ ์ •ํ™•ํžˆ ๋งž์ถœ ์ˆ˜ ์—†๋Š” ์ด์œ ๋Š” ๋ฌด์—‡์ธ๊ฐ€์š”? ํ•œ์ชฝ ๋ฌด๊ฒŒ๊ฐ€ ๋ณด์œ ํ•œ ์›ํŒ๋“ค์˜ ํ•ฉ์œผ๋กœ ๋”ฑ ๋–จ์–ด์ง€์ง€ ์•Š์œผ๋ฉด(์˜ˆ: 0.5ํŒŒ์šด๋“œ ๊ฐ™์€ ์–ด์ค‘๊ฐ„ํ•œ ๊ฐ’), ๊ณ„์‚ฐ๊ธฐ๋Š” ๋ผ์šธ ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๋ฌด๊ฒŒ์™€ ๋‚จ๋Š” ์ฐจ์ด๋ฅผ ํ•จ๊ป˜ ๋ณด์—ฌ์ค๋‹ˆ๋‹ค.

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

์›ํŒ ๊ฐœ์ˆ˜๋Š” ํ•œ์ชฝ ๊ธฐ์ค€์ธ๊ฐ€์š”, ์ „์ฒด ๊ธฐ์ค€์ธ๊ฐ€์š”? ํ‘œ์‹œ๋˜๋Š” ์กฐํ•ฉ๊ณผ ๋ฌด๊ฒŒ๋Š” ๋ชจ๋‘ 'ํ•œ์ชฝ' ๊ธฐ์ค€์ž…๋‹ˆ๋‹ค. ์–‘์ชฝ ๋์— ๋™์ผํ•˜๊ฒŒ ๋ผ์šฐ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

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