Algorithm/BOJ
2022. 3. 7.
[BOJ] ํ์คํ ๊ทธ๋จ(1725)
[๋ฐฑ์ค(BOJ)] ํ์คํ ๊ทธ๋จ(1725) C++ ๋ฌธ์ : BOJ_1725๋ฒ ํ์คํ ๊ทธ๋จ ๋ฌธ์ ์ค๋ช
๋ถํ ์ ๋ณต ์ ๋ช
ํ ๋ถํ ์ ๋ณต ๋ฌธ์ ์
๋๋ค. ์คํ
์ ํ์ฉํ์ฌ O(N) ์์ ํธ๋ ๋ฐฉ๋ฒ๋ ์กด์ฌํ๋ค๊ณ ๋ค์์ผ๋, ๋ถํ ์ ๋ณต์ ์ด์ฉํด ํ์ด๋ดค์ต๋๋ค. ์์์ ํฌ๊ธฐ๋ฅผ ๊ฐ์ง ๊ฐ๊ฒฉ์ด 1์ธ ๋ง๋ ๊ทธ๋ฆฌํ๋ค์ด ๋์ด์ ธ์๊ณ , ๋ด๋ถ์์ ๊ฐ์ฅ ํฐ ๋์ด๋ฅผ ๊ตฌํด์ผ ํ๋๋ฐ ์ด๋, ๋ง๋๊ทธ๋ํ๋ ์ฐ์ํ ๋ง๋๊ทธ๋ํ๋ฅผ ์ ํํด์ผ ํ๊ณ , ๋์ด ๊ฐ์ ์ ํ๋ ๋ง๋๊ทธ๋ํ๋ค ์ค ์ต์ ๋์ด, ๊ฐ๊ฒฉ์ ๋ง๋๊ทธ๋ํ ํ๋์ ๊ฐ๊ฒฉ์ด 1์ด๋ฏ๋ก, ๋ง๋๊ทธ๋ํ์ ๊ฐ์์
๋๋ค. Solution ๋ง๋๊ทธ๋ํ๋ค์ ๊ณ์ ์ ๋ฐ์ฉ ๋๋ ์ ๊ฐ๊ฐ ๋๋ ์ง ์ ๋ฐ๋ง๋ค์ ๊ฒฝ์ฐ์์ ์ต๋ ํฌ๊ธฐ๋ฅผ ๊ตฌํด์ผ ํฉ๋๋ค. ์ด๋, ์ต๋ ํฌ๊ธฐ๋ ์ฒ์์ ๋ง๋๊ทธ๋ํ๋ฅผ ์ค์์ ๊ธฐ์ค์ผ๋ก ์ก๊ณ , ๋์ด๊ฐ ํฐ ์ชฝ(๊ฐ์ ์ชฝ์ด๋ฉด ์๋ฌด ๋ฐ๋)์ผ..