[Python] ๋ฐฑ์ค 1931 - ํ์์ค ๋ฐฐ์
ยท
Algorithm
๋ฌธ์ ํ ๊ฐ์ ํ์์ค์ด ์๋๋ฐ ์ด๋ฅผ ์ฌ์ฉํ๊ณ ์ ํ๋ N๊ฐ์ ํ์์ ๋ํ์ฌ ํ์์ค ์ฌ์ฉํ๋ฅผ ๋ง๋ค๋ ค๊ณ ํ๋ค. ๊ฐ ํ์ I์ ๋ํด ์์์๊ฐ๊ณผ ๋๋๋ ์๊ฐ์ด ์ฃผ์ด์ ธ ์๊ณ , ๊ฐ ํ์๊ฐ ๊ฒน์น์ง ์๊ฒ ํ๋ฉด์ ํ์์ค์ ์ฌ์ฉํ ์ ์๋ ํ์์ ์ต๋ ๊ฐ์๋ฅผ ์ฐพ์๋ณด์. ๋จ, ํ์๋ ํ๋ฒ ์์ํ๋ฉด ์ค๊ฐ์ ์ค๋จ๋ ์ ์์ผ๋ฉฐ ํ ํ์๊ฐ ๋๋๋ ๊ฒ๊ณผ ๋์์ ๋ค์ ํ์๊ฐ ์์๋ ์ ์๋ค. ํ์์ ์์์๊ฐ๊ณผ ๋๋๋ ์๊ฐ์ด ๊ฐ์ ์๋ ์๋ค. ์ด ๊ฒฝ์ฐ์๋ ์์ํ์๋ง์ ๋๋๋ ๊ฒ์ผ๋ก ์๊ฐํ๋ฉด ๋๋ค. ์
๋ ฅ ์ฒซ์งธ ์ค์ ํ์์ ์ N(1 ≤ N ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N+1 ์ค๊น์ง ๊ฐ ํ์์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋๋ฐ ์ด๊ฒ์ ๊ณต๋ฐฑ์ ์ฌ์ด์ ๋๊ณ ํ์์ ์์์๊ฐ๊ณผ ๋๋๋ ์๊ฐ์ด ์ฃผ์ด์ง๋ค. ์์ ์๊ฐ๊ณผ ๋๋๋ ์๊ฐ์ 231-1๋ณด๋ค ์๊ฑฐ..