[c++] BOJ 3108 :: ๋กœ๊ณ 
Algorithm ๋ฌธ์ œ/BOJ 2021. 8. 31. 21:01

๋ฌธ์ œ ๋กœ๊ณ ๋Š” ์ฃผ๋กœ ๊ต์œก์šฉ์— ์“ฐ์ด๋Š” ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด์ด๋‹ค. ๋กœ๊ณ ์˜ ๊ฐ€์žฅ ํฐ ํŠน์ง•์€ ๊ฑฐ๋ถ์ด ๋กœ๋ด‡์ธ๋ฐ, ์‚ฌ์šฉ์ž๋Š” ์ด ๊ฑฐ๋ถ์ด ๋กœ๋ด‡์„ ์›€์ง์ด๋Š” ๋ช…๋ น์„ ์ž…๋ ฅํ•ด ํ™”๋ฉด์— ๋„ํ˜•์„ ๊ทธ๋ฆด ์ˆ˜ ์žˆ๋‹ค. ๊ฑฐ๋ถ์ด๋Š” ์œ„์น˜์™€ ๊ฐ๋„๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ฑฐ๋ถ์ด๋Š” ์ž…์— ์—ฐํ•„์„ ๋ฌผ๊ณ  ์žˆ๋Š”๋ฐ, ์—ฐํ•„์„ ๋‚ด๋ฆฌ๋ฉด ์›€์ง์ผ ๋•Œ ํ™”๋ฉด์— ์„ ์„ ๊ทธ๋ฆฌ๊ณ , ์˜ฌ๋ฆฌ๋ฉด ์„ ์„ ๊ทธ๋ฆฌ์ง€ ์•Š๊ณ  ๊ทธ๋ƒฅ ์ง€๋‚˜๊ฐ€๊ธฐ๋งŒ ํ•œ๋‹ค. ์ œ์ผ ์ฒ˜์Œ์— ๊ฑฐ๋ถ์ด๋Š” (0,0)์— ์žˆ๊ณ , ๊ฑฐ๋ถ์ด๊ฐ€ ๋ณด๊ณ  ์žˆ๋Š” ๋ฐฉํ–ฅ์€ y์ถ•์ด ์ฆ๊ฐ€ํ•˜๋Š” ๋ฐฉํ–ฅ์ด๋‹ค. ๋˜ํ•œ ์—ฐํ•„์€ ๋‚ด๋ฆฌ๊ณ  ์žˆ๋‹ค. ์‚ฌ์šฉ์ž๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‹ค์„ฏ๊ฐ€์ง€ ๋ช…๋ น์œผ๋กœ ๊ฑฐ๋ถ์ด๋ฅผ ์กฐ์ •ํ•  ์ˆ˜ ์žˆ๋‹ค. FD x: ๊ฑฐ๋ถ์ด๋ฅผ x๋งŒํผ ์•ž์œผ๋กœ ์ „์ง„ LT a: ๊ฑฐ๋ถ์ด๋ฅผ ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ a๋„ ๋งŒํผ ํšŒ์ „ RT a: ๊ฑฐ๋ถ์ด๋ฅผ ์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ a๋„ ๋งŒํผ ํšŒ์ „ PU: ์—ฐํ•„์„ ์˜ฌ๋ฆฐ๋‹ค PD: ์—ฐํ•„์„..

[c++] BOJ 1027 :: ๊ณ ์ธต ๊ฑด๋ฌผ
Algorithm ๋ฌธ์ œ/BOJ 2021. 8. 31. 20:59

๋ฌธ์ œ ๊ณ ์ธต ๊ฑด๋ฌผ ๋ฌธ์ œ ๋ฐ”๋กœ๊ฐ€๊ธฐ ์„ธ์ค€์‹œ์—๋Š” ๊ณ ์ธต ๋นŒ๋”ฉ์ด ๋งŽ๋‹ค. ์„ธ์ค€์‹œ์˜ ์„œ๋ฏผ ๊น€์ง€๋ฏผ์€ ๊ฐ€์žฅ ๋งŽ์€ ๊ณ ์ธต ๋นŒ๋”ฉ์ด ๋ณด์ด๋Š” ๊ณ ์ธต ๋นŒ๋”ฉ์„ ์ฐพ์œผ๋ ค๊ณ  ํ•œ๋‹ค. ๋นŒ๋”ฉ์€ ์ด N๊ฐœ๊ฐ€ ์žˆ๋Š”๋ฐ, ๋นŒ๋”ฉ์€ ์„ ๋ถ„์œผ๋กœ ๋‚˜ํƒ€๋‚ธ๋‹ค. i๋ฒˆ์งธ ๋นŒ๋”ฉ (1๋ถ€ํ„ฐ ์‹œ์ž‘)์€ (i,0)๋ถ€ํ„ฐ (i,๋†’์ด)์˜ ์„ ๋ถ„์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๊ณ ์ธต ๋นŒ๋”ฉ A์—์„œ ๋‹ค๋ฅธ ๊ณ ์ธต ๋นŒ๋”ฉ B๊ฐ€ ๋ณผ ์ˆ˜ ์žˆ๋Š” ๋นŒ๋”ฉ์ด ๋˜๋ ค๋ฉด, ๋‘ ์ง€๋ถ•์„ ์ž‡๋Š” ์„ ๋ถ„์ด A์™€ B๋ฅผ ์ œ์™ธํ•œ ๋‹ค๋ฅธ ๊ณ ์ธต ๋นŒ๋”ฉ์„ ์ง€๋‚˜๊ฑฐ๋‚˜ ์ ‘ํ•˜์ง€ ์•Š์•„์•ผ ํ•œ๋‹ค. ๊ฐ€์žฅ ๋งŽ์€ ๊ณ ์ธต ๋นŒ๋”ฉ์ด ๋ณด์ด๋Š” ๋นŒ๋”ฉ์„ ๊ตฌํ•˜๊ณ , ๊ฑฐ๊ธฐ์„œ ๋ณด์ด๋Š” ๋นŒ๋”ฉ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ํ’€์ด ๊ธฐ์šธ๊ธฐ๋ฅผ ๋น„๊ตํ•˜์—ฌ, ๋” ๊ธ‰๊ฒฉํ•œ ๊ธฐ์šธ๊ธฐ๊ฐ€ ๋‚˜์˜ค๋ฉด ๋ณด์ด์ง€ ์•Š๋Š” ๊ฒƒ์œผ๋กœ ํŒ๋‹จ ๊ฐ€์žฅ ๊ธ‰๊ฒฉํ•œ ๊ธฐ์šธ๊ธฐ๋ฅผ ๊ณ„์† ๊ฐฑ์‹  ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ์— ๋Œ€ํ•ด์„œ ๊ฐ๊ฐ ๋ณด์ด๋Š” ๊ฑด๋ฌผ ๊ฐœ์ˆ˜ ๊ณ„์‚ฐ ์˜ฌ๋ ค๋‹ค..