๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๋ถ„ํ• ์ •๋ณต

Algorithm/BOJ 2022. 3. 7. [BOJ] ํžˆ์Šคํ† ๊ทธ๋žจ(1725) [๋ฐฑ์ค€(BOJ)] ํžˆ์Šคํ† ๊ทธ๋žจ(1725) C++ ๋ฌธ์ œ : BOJ_1725๋ฒˆ ํžˆ์Šคํ† ๊ทธ๋žจ ๋ฌธ์ œ ์„ค๋ช… ๋ถ„ํ• ์ •๋ณต ์œ ๋ช…ํ•œ ๋ถ„ํ• ์ •๋ณต ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์Šคํ…์„ ํ™œ์šฉํ•˜์—ฌ O(N) ์•ˆ์— ํ‘ธ๋Š” ๋ฐฉ๋ฒ•๋„ ์กด์žฌํ•œ๋‹ค๊ณ  ๋“ค์—ˆ์œผ๋‚˜, ๋ถ„ํ• ์ •๋ณต์„ ์ด์šฉํ•ด ํ’€์–ด๋ดค์Šต๋‹ˆ๋‹ค. ์ž„์˜์˜ ํฌ๊ธฐ๋ฅผ ๊ฐ€์ง„ ๊ฐ„๊ฒฉ์ด 1์ธ ๋ง‰๋Œ€ ๊ทธ๋ฆฌํ”„๋“ค์ด ๋Š˜์–ด์ ธ์žˆ๊ณ , ๋‚ด๋ถ€์—์„œ ๊ฐ€์žฅ ํฐ ๋„“์ด๋ฅผ ๊ตฌํ•ด์•ผ ํ•˜๋Š”๋ฐ ์ด๋•Œ, ๋ง‰๋Œ€๊ทธ๋ž˜ํ”„๋Š” ์—ฐ์†ํ•œ ๋ง‰๋Œ€๊ทธ๋ž˜ํ”„๋ฅผ ์„ ํƒํ•ด์•ผ ํ•˜๊ณ , ๋†’์ด ๊ฐ’์€ ์„ ํƒ๋œ ๋ง‰๋Œ€๊ทธ๋ž˜ํ”„๋“ค ์ค‘ ์ตœ์†Œ ๋†’์ด, ๊ฐ„๊ฒฉ์€ ๋ง‰๋Œ€๊ทธ๋ž˜ํ”„ ํ•˜๋‚˜์˜ ๊ฐ„๊ฒฉ์ด 1์ด๋ฏ€๋กœ, ๋ง‰๋Œ€๊ทธ๋ž˜ํ”„์˜ ๊ฐœ์ˆ˜์ž…๋‹ˆ๋‹ค. Solution ๋ง‰๋Œ€๊ทธ๋ž˜ํ”„๋“ค์„ ๊ณ„์† ์ ˆ๋ฐ˜์”ฉ ๋‚˜๋ˆ ์„œ ๊ฐ๊ฐ ๋‚˜๋ˆ ์ง„ ์ ˆ๋ฐ˜๋งˆ๋‹ค์˜ ๊ฒฝ์šฐ์—์„œ ์ตœ๋Œ€ ํฌ๊ธฐ๋ฅผ ๊ตฌํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, ์ตœ๋Œ€ ํฌ๊ธฐ๋Š” ์ฒ˜์Œ์— ๋ง‰๋Œ€๊ทธ๋ž˜ํ”„๋ฅผ ์ค‘์•™์„ ๊ธฐ์ค€์œผ๋กœ ์žก๊ณ , ๋†’์ด๊ฐ€ ํฐ ์ชฝ(๊ฐ™์€ ์ชฝ์ด๋ฉด ์•„๋ฌด ๋ฐ๋‚˜)์œผ..
Algorithm/BOJ 2022. 3. 6. [BOJ] ๊ณฑ์…ˆ(1629) [๋ฐฑ์ค€(BOJ)] ๊ณฑ์…ˆ(1629) C++ ๋ฌธ์ œ : BOJ_1629๋ฒˆ ๊ณฑ์…ˆ ๋ฌธ์ œ ์„ค๋ช… ๋ถ„ํ• ์ •๋ณต A, B, C๊ฐ€ ์ฃผ์–ด์ง€๊ณ  , A๋ฅผ B๋ฒˆ ๊ณฑํ•œ ๊ฐ’์„ C๋กœ ๋‚˜๋ˆˆ ๊ฐ’์˜ ๋‚˜๋จธ์ง€๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. B๊ฐ€ ๋งค์šฐ ํฌ๊ธฐ ๋•Œ๋ฌธ์—, B์— ๋งž๊ฒŒ ์—ฌ๋Ÿฌ ๋ฒˆ ๊ณฑํ•ด์ฃผ๋ฉด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚ฉ๋‹ˆ๋‹ค. Solution n์ด ์ง์ˆ˜๋ผ๋ฉด, A^n = A^(n/2) * A^(n/2) n์ด ํ™€์ˆ˜๋ผ๋ฉด, A^n = A^(n/2) * A^(n/2) *A์ธ ๊ฒƒ์„ ์ด์šฉํ•˜์—ฌ ๋ถ„ํ•  ์ •๋ณต ํ•ฉ๋‹ˆ๋‹ค. ๊ฐ’์˜ ํฌ๊ธฐ๋„ ์ด ๋ฌธ์ œ์—์„œ ๋งค์šฐ ์ค‘์š”ํ•œ๋ฐ, A, B, C์˜ ๊ฐ’์ด intํ˜•์˜ ์ตœ๋Œ“๊ฐ’๊นŒ์ง€ ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ, long longํ˜•์œผ๋กœ ํ•ด์ฃผ๊ณ , mod C๋ฅผ ๊ณ„์† ์ˆ˜ํ–‰ํ•ด ์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ €๋Š” ์ด ๋ฌธ์ œ์—์„œ ์ž๊พธ ์˜ค๋‹ต ์ œ์ถœ์ด ๋งŽ์ด ๋๋Š”๋ฐ, n์ด ํ™€์ˆ˜์ผ ๋•Œ A^n = A^(n/2) * A..

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”