๋ฐ๋ฒจ ์ํ ๊ณ์ฐ๊ธฐ๋?
์ด ๋๊ตฌ๋ ๋ชฉํ ์ค๋์ ๋ง์ถ๊ธฐ ์ํด ๋ฐ๋ฒจ ์์ชฝ์ ์ด๋ค ์ํ์ ๋ผ์์ผ ํ๋์ง ์ ํํ๊ฒ ์๋ ค์ค๋๋ค. ๋ฐ์ ์ํ์ ๋ค๋ ์ผ์ ์ด๋ํ ๋๋ง๋ค ์์ญ ๋ฒ์ฉ ๋ฐ๋ณตํ๋ ์์ ๊ณ์ฐ ๋ฌธ์ ์ธ๋ฐ, ์ด ๊ณ์ฐ๊ธฐ๋ ๊ทธ ๊ณ์ฐ์ ์ฆ์ ํด๊ฒฐํด ์ค๋๋ค. ํนํ ๋ฌด๊ฑฐ์ด ์ธํธ ์ฌ์ด์ ์ง์ณ ๋จธ๋ฆฌ๊ฐ ์ ์ ๋์๊ฐ ๋ ์ด๋ฆผ์ง์ ์์ด ๋ฑ ๋ง๊ฒ ์ธํ ํ ์ ์์ฃ . ์ฐธ๊ณ ๋ก ์ด ๊ณ์ฐ๊ธฐ๋ 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 ๋จ์๋ก ๋ง์ถฐ ๋ณด์ธ์).
์ค์ ์์
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) ๋จ์์ ๋๋ค. ์ ํํ ์ํ ์ถ์ฒ์ ๋ฐ์ผ๋ ค๋ฉด ํ์ด๋ ๊ฐ์ผ๋ก ์ ๋ ฅํ์ธ์.