[c++] BOJ 1393๋ฒˆ :: ์Œํ•˜์ฒ ๋„ ๊ตฌ๊ตฌํŒ” (์ฝ”๋“œ, ์ฃผ์˜ํ•  ์ , ํ…Œ์ŠคํŠธ์ผ€์ด์Šค)
Algorithm ๋ฌธ์ œ/BOJ 2020. 5. 2. 09:51

์Œํ•˜์ฒ ๋„ ๊ตฌ๊ตฌํŒ” https://www.acmicpc.net/problem/1393 ์‹œ๊ฐ„ ์ œํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ ์ œ์ถœ ์ •๋‹ต ๋งž์€ ์‚ฌ๋žŒ ์ •๋‹ต ๋น„์œจ 2 ์ดˆ 128 MB 445 64 57 29.082% ๋ฌธ์ œ ์ตœ๋ฐฑ์ค€์€ ์Œํ•˜์ฒ ๋„ ๊ตฌ๊ตฌํŒ”์— ํƒ”๋‹ค. ๋ฌธ์ œ๋Š” ๊ตฌ๊ตฌํŒ”์˜ ๊ธฐ์žฅ์ธ ์กฐ๊ต ๊น€์žฌํ™์ด ๋ฐ˜์ฏค ๋ฏธ์ณ์„œ ์—ด์ฐจ๋ฅผ ๋ฉˆ์ถ”์ง€ ์•Š๋Š”๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ๊ทธ๋ž˜์„œ ์ตœ๋ฐฑ์ค€์€ ๋‹ฌ๋ฆฌ๊ณ  ์žˆ๋Š” ์—ด์ฐจ์—์„œ ๋›ฐ์–ด๋‚ด๋ ค์•ผ ํ•œ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ๋›ฐ์–ด๋‚ด๋ฆด ๋•Œ ์ •๋ฅ˜์žฅ ๊นŒ์ง€ ๊ฑฐ๋ฆฌ๊ฐ€ ๋„ˆ๋ฌด ๋ฉ€๋ฉด ๋งˆ์ด ์•„ํ”Œ ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋ž˜์„œ ์ฒ ๋„๊ฐ€ ์ •๋ฅ˜์žฅ์— ๊ฐ€์žฅ ๋งŽ์ด ๊ทผ์ ‘ํ–ˆ์„ ๋•Œ ๋›ฐ์–ด๋‚ด๋ฆฌ๊ณ ์ž ํ•œ๋‹ค. ์–ด๋””์„œ ๋›ฐ์–ด๋‚ด๋ ค์•ผ ํ•˜๋Š”๊ฐ€? ์ž…๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ์ •๋ฅ˜์žฅ์˜ ์œ„์น˜ x y๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ๋‘˜์งธ ์ค„์—๋Š” ํ˜„์žฌ ์—ด์ฐจ์˜ ์œ„์น˜ X Y์™€ ์—ด์ฐจ๊ฐ€ ์ดˆ๋งˆ๋‹ค ์ด๋™ํ•˜๋Š” x์ขŒํ‘œ y์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์—ด์ฐจ๋Š” ํ•ญ์ƒ ์ง์„ ์œผ๋กœ ์›€์ง์ธ๋‹ค. ์ฃผ์–ด์ง€๋Š”..