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

16201

[๋ฐฑ์ค€/C++] 1620๋ฒˆ : ๋‚˜๋Š”์•ผ ํฌ์ผ“๋ชฌ ๋งˆ์Šคํ„ฐ ์ด๋‹ค์†œ ๋ฌธ์ œ ์˜ค๋ฐ•์‚ฌ : ๊ทธ๋Ÿผ ๋‹ค์†œ์•„ ์ด์ œ ์ง„์ •ํ•œ ํฌ์ผ“๋ชฌ ๋งˆ์Šคํ„ฐ๊ฐ€ ๋˜๊ธฐ ์œ„ํ•ด ๋„๊ฐ์„ ์™„์„ฑ์‹œํ‚ค๋„๋ก ํ•˜์—ฌ๋ผ. ์ผ๋‹จ ๋„ค๊ฐ€ ํ˜„์žฌ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํฌ์ผ“๋ชฌ ๋„๊ฐ์—์„œ ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„์„ ๋ณด๋ฉด ํฌ์ผ“๋ชฌ์˜ ๋ฒˆํ˜ธ๋ฅผ ๋งํ•˜๊ฑฐ๋‚˜, ํฌ์ผ“๋ชฌ์˜ ๋ฒˆํ˜ธ๋ฅผ ๋ณด๋ฉด ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„์„ ๋งํ•˜๋Š” ์—ฐ์Šต์„ ํ•˜๋„๋ก ํ•˜์—ฌ๋ผ. ๋‚˜์˜ ์‹œํ—˜์„ ํ†ต๊ณผํ•˜๋ฉด, ๋‚ด๊ฐ€ ์ƒˆ๋กœ ๋งŒ๋“  ๋„๊ฐ์„ ์ฃผ๋„๋ก ํ•˜๊ฒ ๋„ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ๋„๊ฐ์— ์ˆ˜๋ก๋˜์–ด ์žˆ๋Š” ํฌ์ผ“๋ชฌ์˜ ๊ฐœ์ˆ˜ N์ด๋ž‘ ๋‚ด๊ฐ€ ๋งž์ถฐ์•ผ ํ•˜๋Š” ๋ฌธ์ œ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ ธ. N๊ณผ M์€ 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์•ผ ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ํฌ์ผ“๋ชฌ์˜ ๋ฒˆํ˜ธ๊ฐ€ 1๋ฒˆ์ธ ํฌ์ผ“๋ชฌ๋ถ€ํ„ฐ N๋ฒˆ์— ํ•ด๋‹นํ•˜๋Š” ํฌ์ผ“๋ชฌ๊นŒ์ง€ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ž…๋ ฅ์œผ๋กœ ๋“ค์–ด์™€. ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„์€ ๋ชจ๋‘ ์˜์–ด๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ์žˆ๊ณ , ์ฒซ ๊ธ€์ž๋งŒ ๋Œ€๋ฌธ์ž์ด๊ณ , ๋‚˜๋จธ์ง€ ๋ฌธ์ž๋Š” ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด.. 2021. 9. 12.