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

๋“ฃ๋ณด์žก1

[๋ฐฑ์ค€/C++] 1764๋ฒˆ : ๋“ฃ๋ณด์žก ๋ฌธ์ œ ๊น€์ง„์˜์ด ๋“ฃ๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ๊ณผ, ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ์ด ์ฃผ์–ด์งˆ ๋•Œ, ๋“ฃ๋„ ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๋“ฃ๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ์ˆ˜ N, ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. ์ด์–ด์„œ ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๋“ฃ๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ์ด๋ฆ„๊ณผ, N+2์งธ ์ค„๋ถ€ํ„ฐ ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ์ด๋ฆ„์ด ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ด๋ฆ„์€ ๋„์–ด์“ฐ๊ธฐ ์—†์ด ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ง€๋ฉฐ, ๊ทธ ๊ธธ์ด๋Š” 20 ์ดํ•˜์ด๋‹ค. N, M์€ 500,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋“ฃ๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ์—๋Š” ์ค‘๋ณต๋˜๋Š” ์ด๋ฆ„์ด ์—†์œผ๋ฉฐ, ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ๋„ ๋งˆ์ฐฌ๊ฐ€์ง€์ด๋‹ค. ์ถœ๋ ฅ ๋“ฃ๋ณด์žก์˜ ์ˆ˜์™€ ๊ทธ ๋ช…๋‹จ์„ ์‚ฌ์ „์ˆœ์œผ๋กœ ์ถœ๋ ฅํ•œ๋‹ค. ํ’€์ด ๋ฌธ์ œ ์ œ๋ชฉ ๋ณด๊ณ  ์–ด์ด์—†์–ด์„œ 10๋ถ„๊ฐ„ ์ •์ง€ํ–ˆ๋˜ ๋ฌธ์ œใ…Žใ…‹ใ…‹ใ…‹ set์„ ์‚ฌ์šฉํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ.. 2021. 9. 12.