[PS/๊ทธ๋ฆฌ๋””/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ฒด์œก๋ณต
ยท
learnings/PS
๋ฌธ์ œ ์„ค๋ช… ์ ์‹ฌ์‹œ๊ฐ„์— ๋„๋‘‘์ด ๋“ค์–ด, ์ผ๋ถ€ ํ•™์ƒ์ด ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ–ˆ์Šต๋‹ˆ๋‹ค. ๋‹คํ–‰ํžˆ ์—ฌ๋ฒŒ ์ฒด์œก๋ณต์ด ์žˆ๋Š” ํ•™์ƒ์ด ์ด๋“ค์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๋Š” ์ฒด๊ฒฉ ์ˆœ์œผ๋กœ ๋งค๊ฒจ์ ธ ์žˆ์–ด, ๋ฐ”๋กœ ์•ž๋ฒˆํ˜ธ์˜ ํ•™์ƒ์ด๋‚˜ ๋ฐ”๋กœ ๋’ท๋ฒˆํ˜ธ์˜ ํ•™์ƒ์—๊ฒŒ๋งŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 4๋ฒˆ ํ•™์ƒ์€ 3๋ฒˆ ํ•™์ƒ์ด๋‚˜ 5๋ฒˆ ํ•™์ƒ์—๊ฒŒ๋งŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ฒด์œก๋ณต์ด ์—†์œผ๋ฉด ์ˆ˜์—…์„ ๋“ค์„ ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— ์ฒด์œก๋ณต์„ ์ ์ ˆํžˆ ๋นŒ๋ ค ์ตœ๋Œ€ํ•œ ๋งŽ์€ ํ•™์ƒ์ด ์ฒด์œก์ˆ˜์—…์„ ๋“ค์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ „์ฒด ํ•™์ƒ์˜ ์ˆ˜ n, ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ•œ ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด lost, ์—ฌ๋ฒŒ์˜ ์ฒด์œก๋ณต์„ ๊ฐ€์ ธ์˜จ ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด reserve๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ฒด์œก์ˆ˜์—…์„ ๋“ค์„ ์ˆ˜ ์žˆ๋Š” ํ•™์ƒ์˜ ์ตœ๋Œ“๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ..
[PS/๊ทธ๋ฆฌ๋””/์ฝ”๋“œ์—…] 3120 : ๋ฆฌ๋ชจ์ปจ
ยท
learnings/PS
์ปดํ“จํ„ฐ์‹ค์—์„œ ์ˆ˜์—… ์ค‘์ธ ์ •๋ณด ์„ ์ƒ๋‹˜์€ ๋ƒ‰๋‚œ๋ฐฉ๊ธฐ์˜ ์˜จ๋„๋ฅผ ์กฐ์ ˆํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๋ƒ‰๋‚œ๋ฐฉ๊ธฐ๊ฐ€ ๋ฉ€๋ฆฌ ์žˆ์–ด์„œ ๋ฆฌ๋ชจ์ปจ์œผ๋กœ ์กฐ์ž‘ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ๋ฆฌ๋ชจ์ปจ์˜ ์˜จ๋„ ์กฐ์ ˆ ๋ฒ„ํŠผ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 1) ์˜จ๋„๋ฅผ 1๋„ ์˜ฌ๋ฆฌ๋Š” ๋ฒ„ํŠผ 2) ์˜จ๋„๋ฅผ 1๋„ ๋‚ด๋ฆฌ๋Š” ๋ฒ„ํŠผ 3) ์˜จ๋„๋ฅผ 5๋„ ์˜ฌ๋ฆฌ๋Š” ๋ฒ„ํŠผ 4) ์˜จ๋„๋ฅผ 5๋„ ๋‚ด๋ฆฌ๋Š” ๋ฒ„ํŠผ 5) ์˜จ๋„๋ฅผ 10๋„ ์˜ฌ๋ฆฌ๋Š” ๋ฒ„ํŠผ 6) ์˜จ๋„๋ฅผ 10๋„ ๋‚ด๋ฆฌ๋Š” ๋ฒ„ํŠผ ์ด์™€ ๊ฐ™์ด ์ด 6๊ฐœ์˜ ๋ฒ„ํŠผ์œผ๋กœ ๋ชฉํ‘œ ์˜จ๋„๋ฅผ ์กฐ์ ˆํ•ด์•ผ ํ•œ๋‹ค. ํ˜„์žฌ ์„ค์ • ์˜จ๋„์™€ ๋ณ€๊ฒฝํ•˜๊ณ ์žํ•˜๋Š” ๋ชฉํ‘œ ์˜จ๋„๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ์ด ๋ฒ„ํŠผ๋“ค์„ ์ด์šฉํ•˜์—ฌ ๋ชฉํ‘œ ์˜จ๋„๋กœ ๋ณ€๊ฒฝํ•˜๊ณ ์ž ํ•œ๋‹ค. ์ด ๋•Œ ๋ฒ„ํŠผ ๋ˆ„๋ฆ„์˜ ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•˜์‹œ์˜ค. (์˜ˆ๋ฅผ ๋“ค์–ด, 7๋„์—์„œ 34๋„๋กœ ๋ณ€๊ฒฝํ•˜๋Š” ๊ฒฝ์šฐ, 7 -> 17 -> 27 -> 32 -> 33 -> 34 ์ด๋ ‡๊ฒŒ ์ด 5๋ฒˆ ๋ˆ„๋ฅด๋ฉด ๋œ๋‹ค.) ์ž…๋ ฅ : ํ˜„์žฌ..