[c++] BOJ 18119 :: ๋‹จ์–ด ์•”๊ธฐ
Algorithm ๋ฌธ์ œ/BOJ 2021. 8. 10. 21:58

๋ฌธ์ œ ๋‹จ์–ด ์•”๊ธฐ ๋ฌธ์ œ ๋ฐ”๋กœ๊ฐ€๊ธฐ ์ค€์„์ด๋Š” ์˜์–ด ๋‹จ์–ด๋ฅผ ์™ธ์šฐ๋ ค๊ณ  ํ•œ๋‹ค. ์‚ฌ์ „์—๋Š” N๊ฐ€์ง€ ๋‹จ์–ด๊ฐ€ ์ ํ˜€ ์žˆ๋‹ค. ๋ชจ๋“  ๋‹จ์–ด๋Š” ์†Œ๋ฌธ์ž์ด๋‹ค. ๋‹จ์–ด ์•ˆ์— ์žˆ๋Š” ๋ชจ๋“  ์•ŒํŒŒ๋ฒณ์„ ์•Œ ๋•Œ, ๊ทธ ๋‹จ์–ด๋ฅผ ์™„์ „ํžˆ ์•ˆ๋‹ค๊ณ  ํ•œ๋‹ค. ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ฟผ๋ฆฌ๋“ค์ด ์ฃผ์–ด์ง„๋‹ค. 1 x : ์•ŒํŒŒ๋ฒณ x๋ฅผ ์žŠ๋Š”๋‹ค. 2 x : ์•ŒํŒŒ๋ฒณ x๋ฅผ ๊ธฐ์–ตํ•ด ๋‚ธ๋‹ค. ์ฒ˜์Œ์— ๋ชจ๋“  ์•ŒํŒŒ๋ฒณ์„ ๊ธฐ์–ตํ•˜๋Š” ์ƒํƒœ๊ณ , ๋ชจ์Œ์€ ์™„๋ฒฝํ•˜๊ฒŒ ์™ธ์› ๊ธฐ ๋•Œ๋ฌธ์— ์ ˆ๋Œ€ ์žŠ์ง€ ์•Š๋Š”๋‹ค. ๊ฐ ์ฟผ๋ฆฌ๋งˆ๋‹ค ์™„์ „ํžˆ ์•Œ๊ณ  ์žˆ๋Š” ๋‹จ์–ด์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜์—ฌ๋ผ. ํ’€์ด ๋‹จ์–ด์˜ ๊ธธ์ด๊ฐ€ 10^3์ด๋‚˜ ๋˜๋ฏ€๋กœ ์ผ์ผ์ด ๋น„๊ตํ•˜๊ธฐ ํž˜๋“ฌ bit ์—ฐ์‚ฐ์„ ํ†ตํ•ด ๋น„๊ตํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ์•ˆ ์ƒ๊ฐ ์•ŒํŒŒ๋ฒณ 26์ž๋ฆฌ๋ฅผ bitmap์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ๋•Œ 2^26 < (2^3)^9 < 10^10 ์ด๋ฏ€๋กœ ์ถฉ๋ถ„ํžˆ int ํ˜•์œผ๋กœ ํ‘œํ˜„ ๊ฐ€๋Šฅ ์ฝ”๋“œ #include #incl..