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

๊ณ„์‚ฐ ์ž…๋ ฅ

์ž‘์€ ๊ฐ’๋ถ€ํ„ฐ N๊ฐœ๋ฅผ ์ž…๋ ฅํ•˜์„ธ์š”. ์˜ˆ: 800,1500,2400. ๋งˆ์ง€๋ง‰ ๊ฐ’์ด ์ตœ์ข… ์ด์š”๊ธˆ์ž…๋‹ˆ๋‹ค.

๊ณต์‹

๊ด‘๊ณ 

๊ฒฐ๊ณผ

์ด์š”๊ธˆ
2,400
์—” (์•„๋ž˜์—์„œ ๋ถ„๋ฐฐ)
์Šน๊ฐ (ํ•˜์ฐจ ์ˆœ์„œ) ๋ถ€๋‹ด์•ก (์—”)
Passenger 1 270
Passenger 2 620
Passenger 3 (last, absorbs remainder) 1,510
๋ถ„๋ฐฐ์•ก ํ•ฉ๊ณ„ 2,400

๊ฐ ๊ตฌ๊ฐ„ ์š”๊ธˆ์€ ๊ทธ ๊ตฌ๊ฐ„์— ํ•จ๊ป˜ ํƒ„ ์‚ฌ๋žŒ๋“ค๋ผ๋ฆฌ ๊ท ๋“ฑํ•˜๊ฒŒ ๋‚˜๋ˆ„๊ณ  10์—” ๋‹จ์œ„๋กœ ์˜ฌ๋ฆผํ•ฉ๋‹ˆ๋‹ค. ์˜ฌ๋ฆผ์œผ๋กœ ์ƒ๊ธด ์ฐจ์•ก์€ ๋งˆ์ง€๋ง‰ ์Šน๊ฐ์ด ๋ถ€๋‹ดํ•˜์—ฌ ์ „์ฒด ํ•ฉ๊ณ„๊ฐ€ ๋ฏธํ„ฐ๊ธฐ ์š”๊ธˆ๊ณผ ์ •ํ™•ํžˆ ์ผ์น˜ํ•˜๋„๋ก ํ•ฉ๋‹ˆ๋‹ค.

์ด ๊ณ„์‚ฐ๊ธฐ๋Š” ๋ฌด์—‡์„ ํ•˜๋‚˜์š”?

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

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

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

์Šน๊ฐ ์ˆ˜(N)์™€ ๊ฐ ํ•˜์ฐจ ์‹œ์ ์˜ ๋ฏธํ„ฐ๊ธฐ ๋ˆ„์  ๊ธˆ์•ก์„ ์ž‘์€ ๊ฐ’๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ์‰ผํ‘œ๋กœ ๊ตฌ๋ถ„ํ•ด ์ž…๋ ฅํ•˜์„ธ์š”. ์ฒซ ๋ฒˆ์งธ ๊ฐ’์€ ์ฒซ ๋ฒˆ์งธ ์‚ฌ๋žŒ์ด ๋‚ด๋ฆด ๋•Œ์˜ ๋ฏธํ„ฐ๊ธฐ ํ•ฉ๊ณ„์ด๊ณ , ๋งˆ์ง€๋ง‰ ๊ฐ’์€ ์ตœ์ข… ์ด์š”๊ธˆ์ž…๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์„ธ ๋ช…์ด ํƒ”๋‹ค๋ฉด 800,1500,2400์ฒ˜๋Ÿผ ์ž…๋ ฅํ•ฉ๋‹ˆ๋‹ค.

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

\(m_0 = 0\)์œผ๋กœ ๋‘๊ณ , \(m_k\)๋ฅผ \(k\)๋ฒˆ์งธ ํ•˜์ฐจ ์‹œ์ ์˜ ๋ฏธํ„ฐ๊ธฐ ๋ˆ„์  ๊ธˆ์•ก์ด๋ผ๊ณ  ํ•ฉ์‹œ๋‹ค. \(k\)๋ฒˆ์งธ ๊ตฌ๊ฐ„์˜ ์š”๊ธˆ์€ \(f_k = m_k - m_{k-1}\)์ž…๋‹ˆ๋‹ค. ์ด ๊ตฌ๊ฐ„ ๋™์•ˆ์—๋Š” \(N - k + 1\)๋ช…์ด ์•„์ง ํƒ€๊ณ  ์žˆ์œผ๋ฏ€๋กœ, ๊ฐ์ž \(\left\lceil \frac{f_k}{10 \times \text{ํƒ‘์Šน ์ธ์›}} \right\rceil \times 10\)์—”์„ ๋ƒ…๋‹ˆ๋‹ค. ์ฆ‰ ๊ตฌ๊ฐ„ ์š”๊ธˆ์„ ํƒ‘์Šน ์ธ์›์œผ๋กœ ๋‚˜๋ˆˆ ๋’ค 10์—” ๋‹จ์œ„๋กœ ์˜ฌ๋ฆผํ•œ ๊ธˆ์•ก์ž…๋‹ˆ๋‹ค. ์˜ฌ๋ฆผ ๋•Œ๋ฌธ์— ํ•ฉ๊ณ„๊ฐ€ ์•ฝ๊ฐ„ ์ดˆ๊ณผ๋  ์ˆ˜ ์žˆ๋Š”๋ฐ, ์ด ์ฐจ์•ก์€ ๋งˆ์ง€๋ง‰ ์Šน๊ฐ์ด ๋ถ€๋‹ดํ•ฉ๋‹ˆ๋‹ค. ๋งˆ์ง€๋ง‰ ์Šน๊ฐ์˜ ๋ถ€๋‹ด์•ก์€ ์ด์š”๊ธˆ์—์„œ ๋‚˜๋จธ์ง€ ์‚ฌ๋žŒ๋“ค์˜ ์˜ฌ๋ฆผ๋œ ๊ธˆ์•ก์„ ๋บ€ ๊ฐ’์œผ๋กœ ์ •ํ•ด์ง€๋ฏ€๋กœ, ์ „์ฒด ํ•ฉ๊ณ„๋Š” ํ•ญ์ƒ ๋ฏธํ„ฐ๊ธฐ ์š”๊ธˆ๊ณผ ์ •ํ™•ํžˆ ์ผ์น˜ํ•ฉ๋‹ˆ๋‹ค. ๋ˆ„์  ๋ถ€๋‹ด์•ก์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ณ„์‚ฐ๋ฉ๋‹ˆ๋‹ค.

$$\text{Share}_j = \sum_{k=1}^{j} 10\left\lceil \frac{m_k - m_{k-1}}{\,N - k + 1\,} \right\rceil$$

$$\text{where}\quad \left\{ \begin{aligned} m_k &= \text{Meter at drop-off } k \text{ (yen)} \\ m_0 &= 0 \\ \text{leg } k &= m_k - m_{k-1} \text{ split among } N-k+1 \text{ riders} \end{aligned} \right.$$

ํ•œ ๊ตฌ๊ฐ„ ์š”๊ธˆ์„ ๋‚จ์€ ์Šน๊ฐ๋ผ๋ฆฌ ๋‚˜๋ˆˆ ๋’ค ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด 10์—” ๋‹จ์œ„๋กœ ์˜ฌ๋ฆผํ•˜๋Š” ๊ณผ์ •์„ ๋ณด์—ฌ์ฃผ๋Š” ๋„ํ‘œ
ํ•œ ๊ตฌ๊ฐ„์˜ ์ถ”๊ฐ€ ์š”๊ธˆ์€ ํƒ‘์Šน ์ค‘์ธ ์Šน๊ฐ๋ผ๋ฆฌ ๋˜‘๊ฐ™์ด ๋‚˜๋ˆ„๊ณ , ๊ฐ์ž์˜ ๋ถ€๋‹ด์•ก์€ 10์—” ๋‹จ์œ„๋กœ ์˜ฌ๋ฆผํ•ฉ๋‹ˆ๋‹ค.

์‹ค์ œ ๊ณ„์‚ฐ ์˜ˆ์‹œ

์Šน๊ฐ ์„ธ ๋ช…, ๋ฏธํ„ฐ๊ธฐ ๊ธˆ์•ก 800, 1500, 2400. 1๊ตฌ๊ฐ„(3๋ช…): \(800/3 = 266.67\) โ†’ ๊ฐ์ž 270์—”์œผ๋กœ ์˜ฌ๋ฆผ. 2๊ตฌ๊ฐ„(2๋ช…): \(700/2 = 350\)์—”์”ฉ. 3๊ตฌ๊ฐ„(1๋ช…): 900์—”. ์ž ์ • ํ•ฉ๊ณ„: \(P_1 = 270\), \(P_2 = 620\), \(P_3 = 1520\) (ํ•ฉ๊ณ„ 2410). ๋งˆ์ง€๋ง‰ ์‚ฌ๋žŒ์ด ์ดˆ๊ณผ๋œ 10์—”์„ ๋ถ€๋‹ดํ•ฉ๋‹ˆ๋‹ค: \(P_3 = 2400 - (270 + 620) = 1510\). ์ตœ์ข… ๊ฒฐ๊ณผ: \(P_1\)์€ 270์—”, \(P_2\)๋Š” 620์—”, \(P_3\)๋Š” 1510์—”, ํ•ฉ๊ณ„ 2400์—”.

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

๋ˆ„๊ฐ€ ๊ฐ€์žฅ ๋งŽ์ด ๋‚ด๋‚˜์š”? ๋ณดํ†ต ๋งˆ์ง€๋ง‰์— ๋‚ด๋ฆฌ๋Š” ์‚ฌ๋žŒ์ž…๋‹ˆ๋‹ค. ๋ชจ๋“  ๊ตฌ๊ฐ„์„ ํ•จ๊ป˜ ํƒ”์„ ๋ฟ ์•„๋‹ˆ๋ผ ์˜ฌ๋ฆผ์œผ๋กœ ์ƒ๊ธด ์ฐจ์•ก๊นŒ์ง€ ๋– ์•ˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.

์™œ 10์—” ๋‹จ์œ„๋กœ ์˜ฌ๋ฆผํ•˜๋‚˜์š”? ์ผ๋ณธ์˜ ํ˜„๊ธˆ ๊ฒฐ์ œ์™€ ํ•ฉ์Šน ์š”๊ธˆ ์ •์‚ฐ ๊ด€์Šต์ด 10์—” ๋‹จ์œ„๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์˜ฌ๋ฆผ ์ฒ˜๋ฆฌํ•˜๋ฉด 1์—” ๋‹จ์œ„ ์ž”๋ˆ์ด ์ƒ๊ธฐ์ง€ ์•Š์•„ ๊ฐ€์žฅ ํ”ํžˆ ์“ฐ์ด๋Š” ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค.

ํ•ญ์ƒ ์™„๋ฒฝํ•˜๊ฒŒ ๊ณต์ •ํ•œ๊ฐ€์š”? ์ด ๋ฐฉ์‹์€ ๊ฐ€๊นŒ์šด ๊ณณ๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ๋‚ด๋ฆฐ๋‹ค๊ณ  ๊ฐ€์ •ํ•ฉ๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์šฐํšŒ ๋•Œ๋ฌธ์— ์•ž์ชฝ ์ •๋ฅ˜ ๊ตฌ๊ฐ„์ด ๋” ๋น„์‹ธ์ง„๋‹ค๋ฉด, ์ค‘๊ฐ„์— ๋‚ด๋ฆฐ ์Šน๊ฐ์ด ์•ฝ๊ฐ„ ๋” ๋งŽ์ด ๋‚ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ตฌ๊ฐ„๋ณ„ ๊ท ๋“ฑ ๋ถ„๋ฐฐ ๋ฐฉ์‹์ด ๊ฐ€์ง„ ๋ณธ์งˆ์ ์ธ ํ•œ๊ณ„์ž…๋‹ˆ๋‹ค.

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