[Python] ๋ฐฑ์ค€ 1931 - ํšŒ์˜์‹ค ๋ฐฐ์ •
ยท
Algorithm
๋ฌธ์ œ ํ•œ ๊ฐœ์˜ ํšŒ์˜์‹ค์ด ์žˆ๋Š”๋ฐ ์ด๋ฅผ ์‚ฌ์šฉํ•˜๊ณ ์ž ํ•˜๋Š” N๊ฐœ์˜ ํšŒ์˜์— ๋Œ€ํ•˜์—ฌ ํšŒ์˜์‹ค ์‚ฌ์šฉํ‘œ๋ฅผ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ๊ฐ ํšŒ์˜ I์— ๋Œ€ํ•ด ์‹œ์ž‘์‹œ๊ฐ„๊ณผ ๋๋‚˜๋Š” ์‹œ๊ฐ„์ด ์ฃผ์–ด์ ธ ์žˆ๊ณ , ๊ฐ ํšŒ์˜๊ฐ€ ๊ฒน์น˜์ง€ ์•Š๊ฒŒ ํ•˜๋ฉด์„œ ํšŒ์˜์‹ค์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ํšŒ์˜์˜ ์ตœ๋Œ€ ๊ฐœ์ˆ˜๋ฅผ ์ฐพ์•„๋ณด์ž. ๋‹จ, ํšŒ์˜๋Š” ํ•œ๋ฒˆ ์‹œ์ž‘ํ•˜๋ฉด ์ค‘๊ฐ„์— ์ค‘๋‹จ๋  ์ˆ˜ ์—†์œผ๋ฉฐ ํ•œ ํšŒ์˜๊ฐ€ ๋๋‚˜๋Š” ๊ฒƒ๊ณผ ๋™์‹œ์— ๋‹ค์Œ ํšŒ์˜๊ฐ€ ์‹œ์ž‘๋  ์ˆ˜ ์žˆ๋‹ค. ํšŒ์˜์˜ ์‹œ์ž‘์‹œ๊ฐ„๊ณผ ๋๋‚˜๋Š” ์‹œ๊ฐ„์ด ๊ฐ™์„ ์ˆ˜๋„ ์žˆ๋‹ค. ์ด ๊ฒฝ์šฐ์—๋Š” ์‹œ์ž‘ํ•˜์ž๋งˆ์ž ๋๋‚˜๋Š” ๊ฒƒ์œผ๋กœ ์ƒ๊ฐํ•˜๋ฉด ๋œ๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ํšŒ์˜์˜ ์ˆ˜ N(1 ≤ N ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N+1 ์ค„๊นŒ์ง€ ๊ฐ ํšŒ์˜์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ ์ด๊ฒƒ์€ ๊ณต๋ฐฑ์„ ์‚ฌ์ด์— ๋‘๊ณ  ํšŒ์˜์˜ ์‹œ์ž‘์‹œ๊ฐ„๊ณผ ๋๋‚˜๋Š” ์‹œ๊ฐ„์ด ์ฃผ์–ด์ง„๋‹ค. ์‹œ์ž‘ ์‹œ๊ฐ„๊ณผ ๋๋‚˜๋Š” ์‹œ๊ฐ„์€ 231-1๋ณด๋‹ค ์ž‘๊ฑฐ..