๋ฌธ์ ๋๋์ ์ขํ ๋ฐ์ดํฐ๋ฅผ ๋ฉ๋ชจ๋ฆฌ ์์ ์์ถํด ์ ์ฅํ๊ธฐ ์ํด ์ฌ์ฉํ๋ ์ฌ๋ฌ ๊ธฐ๋ฒ ์ค ์ฟผ๋ ํธ๋ฆฌ(quad tree)๋ ๊ฒ์ด ์์ต๋๋ค. ์ฃผ์ด์ง ๊ณต๊ฐ์ ํญ์ 4๊ฐ๋ก ๋ถํ ํด ์ฌ๊ท์ ์ผ๋ก ํํํ๊ธฐ ๋๋ฌธ์ ์ฟผ๋ ํธ๋ฆฌ๋ผ๋ ์ด๋ฆ์ด ๋ถ์๋๋ฐ, ์ด์ ์ ๋ช
ํ ์ฌ์ฉ์ฒ ์ค ํ๋๋ ๊ฒ์ ์๊ณผ ํฐ ์๋ฐ์ ์๋ ํ๋ฐฑ ๊ทธ๋ฆผ์ ์์ถํด ํํํ๋ ๊ฒ์
๋๋ค. ์ฟผ๋ ํธ๋ฆฌ๋ 2N × 2N ํฌ๊ธฐ์ ํ๋ฐฑ ๊ทธ๋ฆผ์ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ ๊ฑฐ์ณ ๋ฌธ์์ด๋ก ์์ถํฉ๋๋ค. ์ด ๊ทธ๋ฆผ์ ๋ชจ๋ ํฝ์
์ด ๊ฒ์ ์์ผ ๊ฒฝ์ฐ ์ด ๊ทธ๋ฆผ์ ์ฟผ๋ ํธ๋ฆฌ ์์ถ ๊ฒฐ๊ณผ๋ ๊ทธ๋ฆผ์ ํฌ๊ธฐ์ ๊ด๊ณ์์ด b๊ฐ ๋ฉ๋๋ค. ์ด ๊ทธ๋ฆผ์ ๋ชจ๋ ํฝ์
์ด ํฐ ์์ผ ๊ฒฝ์ฐ ์ด ๊ทธ๋ฆผ์ ์ฟผ๋ ํธ๋ฆฌ ์์ถ ๊ฒฐ๊ณผ๋ ๊ทธ๋ฆผ์ ํฌ๊ธฐ์ ๊ด๊ณ์์ด w๊ฐ ๋ฉ๋๋ค. ๋ชจ๋ ํฝ์
์ด ๊ฐ์ ์์ด ์๋๋ผ๋ฉด, ์ฟผ๋ ํธ๋ฆฌ๋ ์ด ๊ทธ๋ฆผ์ ๊ฐ๋ก ์ธ๋ก๋ก ๊ฐ๊ฐ 2..
๋ถ๋ฅ ์ ์ฒด๋ณด๊ธฐ
๋ํ๊ต 2ํ๋
๋๋ ๋ค์ํ ์ข
๋ฅ์ stl์ ์ฌ์ฉํ๋๋ฐ, ๋ง์ ์๊ณ ๋ฆฌ์ฆ ๊ณต๋ถ๋ฅผ ํ๋ค ๋ณด๋ stl์ ์ฌ์ฉํ๋ ํ์๊ฐ ์ ์ด์ ธ์ ์ด๋ ๊ฒ๋๋ง ์ ๋ฆฌํ๋ ค๊ณ ํ๋ค. List๋ sequence container๋ก ์์์๊ฐ ์ฝ์
๊ณผ ์ญ์ ์ฐ์ฐ์ ํ ์ ์๋ค. ๋จ์ํ ๋งํด์ ๋งํฌ๋ ๋ฆฌ์คํธ์ stl ๋ฒ์ ์ด๋ผ๊ณ ์๊ฐํ๋ฉด ๋ ๊ฒ ๊ฐ๋ค. doubly-linked list๋ก ๊ตฌ์ฑ๋์ด ์๋ค. ๋ฉค๋ฒ ํจ์๋ ๋ค์๊ณผ ๊ฐ๋ค(์ผ๋ถ๋ง ์์ ) begin iterator์ ์์๋ถ๋ถ์ returnํ๋ค end iterator์ ๋๋ถ๋ถ์ returnํ๋ค empty list๊ฐ ๋น์๋์ง ์๋ ค์ค size list์ ์์ ๊ฐ์ front ์ฒซ๋ฒ์งธ ์์์ ์ ๊ทผํ๋ค back ๋ง์ง๋ง ์์์ ์ ๊ทผํ๋ค assign ์๋กญ๊ฒ list๋ฅผ ํ ๋นํ๋ค(์์์ ๊ฐ) push_front..
๋ฌธ์ ๋ ๊ฐ์ ์์ฐ์๋ฅผ ์
๋ ฅ๋ฐ์ ์ต๋ ๊ณต์ฝ์์ ์ต์ ๊ณต๋ฐฐ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์
๋ ฅ ์ฒซ์งธ ์ค์๋ ๋ ๊ฐ์ ์์ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ์ด ๋์ 10,000์ดํ์ ์์ฐ์์ด๋ฉฐ ์ฌ์ด์ ํ ์นธ์ ๊ณต๋ฐฑ์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์๋ ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง ๋ ์์ ์ต๋๊ณต์ฝ์๋ฅผ,๋์งธ ์ค์๋ ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง ๋ ์์ ์ต์ ๊ณต๋ฐฐ์๋ฅผ ์ถ๋ ฅํ๋ค. ์์ ์
๋ ฅ 24 18 ์์ ์ถ๋ ฅ 6 72 ๋ฌธ์ ํ์ด ์ฒ์์ ๋จ์ํ ํ๋์ ์ฝ์๋ฅผ ๊ตฌํด์ ์ต๋ ๊ณต์ฝ์๋ฅผ ๊ตฌํ๋ ๋ฐฉ๋ฒ์ผ๋ก ์ ๊ฐํ๋ค. ํ์ง๋ง ์ธํฐ๋ท์ ์ฐพ์๋ณด๋ ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ด๋ผ๋ ๊ฒ์ ์์ ๋ผ ์ ์์๋ค. ...๋๋ณด๊ธฐ ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ(- ไบ้คๆณ, Euclidean algorithm)์ 2๊ฐ์ ์์ฐ์ ๋๋ ์ ์(ๆดๅผ)์ ์ต๋๊ณต์ฝ์๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ ํ๋์ด๋ค. ํธ์ ๋ฒ์ด๋ ๋ง์ ๋ ์๊ฐ ..
๋ฌธ์ ๋น์ด์๋ ๊ณต์งํฉ S๊ฐ ์ฃผ์ด์ก์ ๋, ์๋ ์ฐ์ฐ์ ์ํํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. add x: S์ x๋ฅผ ์ถ๊ฐํ๋ค. (1 ≤ x ≤ 20) S์ x๊ฐ ์ด๋ฏธ ์๋ ๊ฒฝ์ฐ์๋ ์ฐ์ฐ์ ๋ฌด์ํ๋ค. remove x: S์์ x๋ฅผ ์ ๊ฑฐํ๋ค. (1 ≤ x ≤ 20) S์ x๊ฐ ์๋ ๊ฒฝ์ฐ์๋ ์ฐ์ฐ์ ๋ฌด์ํ๋ค. check x: S์ x๊ฐ ์์ผ๋ฉด 1์, ์์ผ๋ฉด 0์ ์ถ๋ ฅํ๋ค. toggle x: S์ x๊ฐ ์์ผ๋ฉด x๋ฅผ ์ ๊ฑฐํ๊ณ , ์์ผ๋ฉด x๋ฅผ ์ถ๊ฐํ๋ค. (1 ≤ x ≤ 20) all: S๋ฅผ {1, 2, ..., 20} ์ผ๋ก ๋ฐ๊พผ๋ค. empty: S๋ฅผ ๊ณต์งํฉ์ผ๋ก ๋ฐ๊พผ๋ค ์
๋ ฅ ์ฒซ์งธ ์ค์ ์ํํด์ผ ํ๋ ์ฐ์ฐ์ ์ M (1 ≤ M ≤ 3,000,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ์ํํด์ผ ํ๋ ์ฐ์ฐ์ด ํ ์ค์ ํ๋์ฉ ์ฃผ..
๋ฌธ์ ์๋์ ์๋ ๋
ธํธ๋ถ์ ์ ์กฐํ๊ณ ํ๋งคํ๋ ํ์ฌ์ด๋ค. ๋
ธํธ๋ถ ํ๋งค ๋์์ ์๊ด์์ด ๋งค๋
์๋๋ฃ, ์ฌ์ฐ์ธ, ๋ณดํ๋ฃ, ๊ธ์ฌ ๋ฑ A๋ง์์ ๊ณ ์ ๋น์ฉ์ด ๋ค๋ฉฐ, ํ ๋์ ๋
ธํธ๋ถ์ ์์ฐํ๋ ๋ฐ์๋ ์ฌ๋ฃ๋น์ ์ธ๊ฑด๋น ๋ฑ ์ด B๋ง์์ ๊ฐ๋ณ ๋น์ฉ์ด ๋ ๋ค๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด A=1,000, B=70์ด๋ผ๊ณ ํ์. ์ด ๊ฒฝ์ฐ ๋
ธํธ๋ถ์ ํ ๋ ์์ฐํ๋ ๋ฐ๋ ์ด 1,070๋ง์์ด ๋ค๋ฉฐ, ์ด ๋ ์์ฐํ๋ ๋ฐ๋ ์ด 1,700๋ง์์ด ๋ ๋ค. ๋
ธํธ๋ถ ๊ฐ๊ฒฉ์ด C๋ง์์ผ๋ก ์ฑ
์ ๋์๋ค๊ณ ํ๋ค. ์ผ๋ฐ์ ์ผ๋ก ์์ฐ ๋์๋ฅผ ๋๋ ค ๊ฐ๋ค ๋ณด๋ฉด ์ด๋ ์๊ฐ ์ด ์์
(ํ๋งค๋น์ฉ)์ด ์ด ๋น์ฉ(=๊ณ ์ ๋น์ฉ+๊ฐ๋ณ๋น์ฉ)๋ณด๋ค ๋ง์์ง๊ฒ ๋๋ค. ์ต์ด๋ก ์ด ์์
์ด ์ด ๋น์ฉ๋ณด๋ค ๋ง์์ ธ ์ด์ต์ด ๋ฐ์ํ๋ ์ง์ ์ ์์ต๋ถ๊ธฐ์ (BREAK-EVEN POINT)์ด๋ผ๊ณ ํ๋ค. A, B, C๊ฐ ์ฃผ์ด์ก..