์ฝ์นญ ๋ชฉํ
- ์๊ฐ์์ ๋ฌธ์ ํด๊ฒฐ๋ฅ๋ ฅ์ ์ฆ์ง์ํจ๋ค.(์ด๋ ํ ์ฒ์ ๋ณด๋ ๋ฌธ์ ๋ผ๋ ํ ์ ์๋๋ก ํ๋ค.)
- Lev.20๊น์ง ๋๋ฌํ๊ฒ ํจ์ผ๋ก์จ ๋ค์ํ ์๊ณ ๋ฆฌ์ฆ์ ์ตํ๊ฒ ํ๋ค.
- ์ฝ๋ฉ ํ
์คํธ์ ํฉ๊ฒฉํ ์ ์๊ฒ ํ๋ค.
๋ฌธ์ ํด๊ฒฐ์ ์ฐจ
- ๋ฌธ์ ๋ฅผ ์ดํดํ๋ค. (๋ฌธ์ ์์ ๊ตฌํด์ผ๋๋ ๊ฐ์ ์ ์ํ๊ณ , ํด๋น ๊ฐ์ด ๋์ฌ ์ ์๋ ๋ชจ๋ ์ํฉ์ ์๊ฐํด๋ณธ๋ค)
- ํ์ด๋ฒ์ ๊ฐ๋ฐํ๋ค. (๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋๋ฐ ํ์ํ ์ ์ฐจ ๋ฐ ์๊ณ ๋ฆฌ์ฆ์ ์ค๊ณํ๋ค, Bruteforce ๋ถํฐ ์ ์ฉ)
- ๋ง๋ ํ์ด๋ฒ์ด ๋ฌธ์ ๋ฅผ ์ ๋๋ก ํด๊ฒฐํ๋์ง ๊ฒํ ํ๋ค. (์ดํดํ ๋ฌธ์ ๋ฅผ ํ์ด๋ฒ์ ํตํด ๋ชจ๋ ๊ตฌํ ์ ์๋์ง)
- ์ ํ๋ ์ํฉ์์ ์ ๋๋ก ๋์ํ๋์ง ๊ฒํ ํ๋ค. (์
๋ ฅํฌ๊ธฐ ์ ํ, ์๊ฐ๋ณต์ก๋, ๊ณต๊ฐ๋ณต์ก๋, ๋ฉ๋ชจ๋ฆฌ ์ ํ)
- ์ฝ๋๋ก ๊ตฌํํ๋ค. (ํ์ด๋ฒ์ ์ฝ๋๋ก ์ฎ๊ธด๋ค)
- 100์ ์ ๋ฐ๋๋ค.
์ฝ์น ์
๋ฌด
- ์ฝ์น๊ฐ ๋ชฉํ๋ฅผ ์ด๋ฃจ๊ธฐ ์ํด ํด์ผ๋ ์ผ์ ํฌ๊ฒ 2๊ฐ์ง์ด๋ค.
-
์ง์ ์๋ต
- ์ฝ์น๋ ์ง์ ์๋ต ๊ณผ์ ์ ํตํด ์๊ฐ์์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํจ์ ์์ด์ ์ฌ๊ณ ์ ํ๋ฆ ์ค ์ด๋ ๋ถ๋ถ์ด ์ฝํ์ง ๋น ๋ฅด๊ฒ ํ์
ํ์ฌ ํด๋น ๋ถ๋ถ์ Develop ํ ์ ์๋๋ก ๋์์ค๋ค.
- ์ฝ์น๋ ์๊ฐ์์ด ๋ง๋ค์ด์จ ๋ชจ๋ ์ง๋ฌธ์ ๋ํ ๋ต๋ณ์ ํด์ค ์ ์์ด์ผํ๋ฉฐ ์๊ฐ์์ ๋ต๋ณ์ ์ป์์ผ๋ก ์ค์ค๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ ํ์ด ๊ธธ๋ฌ์ ธ์ผํ๋ค.(๋ต๋ณ์ ๋ฐ์์ผ๋ก ๊ณ ๋ฏผํด๋ณผ ์ ์์ด์ผํ๋ค. ๋ต๋ณ์ ์ง์ด ์๊ฐ์์ด ๋ง์กฑํ ์ ๋์ฌ์ผ ํ๋ค.)
- ์ฝ์น๊ฐ ์๊ฐ์์ด ๋ง๋ค์ด์จ ๋ชจ๋ ์ง๋ฌธ์ ๋ํ ๋ต๋ณ์ ์ค ์ ์์ผ๋ ค๋ฉด ์ง๋ฌธ์ด ๋ช ๊ฐ๊ฐ ๋์ฌ์ง ์๊ณ ์์ผ๋ฉด ์ข๋ค.
- ๋ต๋ณ์ ์ง์ ์ง๋ฌธ์ ๋ํด ์๊ฐํ ์ ์๋ ์๊ฐ์ด ๋ง์ผ๋ฉด ๋ง์์๋ก ๋์์ง ๊ฐ๋ฅ์ฑ์ด ์๋ค. ๋ฐ๋ผ์ ์ฝ์น๋ ์๊ฐ์์ด ์ด๋ค ์ง๋ฌธ์ ํ ๊ฒ์ธ์ง ์๊ณ ์์ผ๋ฉด ์ข๋ค.
- ์๊ฐ์์ ์ง๋ฌธ์ ์๊ฐ์์ด ์ด๋ค ๋ฌธ์ ๋ฅผ ์๋(a)ํ๊ฑฐ๋ ํ์ด์๋์ง(b)๋ฅผ ์๋ฉด ํ์
ํ ์ ์๋ค.
- ๋ฐ๋ผ์, ์ฝ์น๋ ์ฝ์นญย ์ ์๊ฐ์์ ์ ์ถ ๊ธฐ๋ก(b) / ์ปดํ์ผ ๊ธฐ๋ก(a) / ๋ฉ๋ชจ ๊ธฐ๋ก(a) / ๋ฌธ์ ๋ฅผ ์ด์๋์ง(a)์ ๋ํ ๊ธฐ๋ก์ ์๋ฉด ์ด๋ค ์ง๋ฌธ์ ํ๊ณ ๋ช ๊ฐ์ ์ง๋ฌธ์ ํ ์ง ์์ธกํ ์ ์๋ค.
- ๋ฌธ์ ๋ฅผ ์ด์๋์ง
- ๋ฌธ์ ๋ฅผ ์ด์์ผ๋ ํ์ด์ค์ง ์์ ๊ฒฝ์ฐ๋
- ๋ฌธ์ ๋ฅผ ๋ฉด๋ฐํ ๋ณด์ง์์๊ฑฐ๋,
- ๋ฌธ์ ๋ฅผ ๋ฉด๋ฐํ ๋ดค์ผ๋ ๋ฌธ์ ์ ์ํ๋ ๊ฒ์ด ๋ญ์ง ์ดํด(1)๊ฐ ์๋ ๊ฒ์ด๋ค.
- ๋ฉ๋ชจ ๊ธฐ๋ก
- ๋ฉ๋ชจ ๊ธฐ๋ก์ด ์๋ค๋ ๊ฒ์
- ๋ฌธ์ ๋ฅผ ์๊ธฐ๋๋ฆ๋๋ก ์ดํดํ๊ณ (1), ํ์ด๋ฒ์ ๊ฐ๋ฐํ์ ์๋ ์๊ณ (2), ๊ฒํ (3, 4)๊น์ง ๋ ์ํฉ์ผ ์ ์๋ค.
- ๋ฉ๋ชจ ๊ธฐ๋ก์ ์ฝ์ด๋ณด๋ฉด
- ๋ฌธ์ ๋ฅผ ์ ์ดํดํ๋์ง(1), ํ์ด๋ฒ์ ๊ฐ๋ฐํ๋์ง(2), ๊ฐ๋ฐํ ํ์ด๋ฒ์ด ์ ์ ํ์ง(3), ๋ฌธ์ ์ ์ฃผ์ด์ง ์ ํ์ ํ์ด๋ฒ์ด ์ ์ ํ์ง(4)๋ฅผ ์ ์ ์๋ค.
- ์ปดํ์ผ ๊ธฐ๋ก
- ์ปดํ์ผ ๊ธฐ๋ก์ด ์๋ค๋ ๊ฒ์
- ๋ฌธ์ ๋ฅผ ์๊ธฐ๋๋ฆ๋๋ก ์ดํดํ๊ณ (1), ์ฝ๋๊ฐ ๊ตฌํ(5)๋ ์ํฉ์ด๋ค. (ํ์ด๋ฒ์ด ์์ ํ์ง(2), ๊ฒํ (3, 4)๋ ํ๋์ง ๋ชจ๋ฅธ๋ค)
- ์ปดํ์ผํ ์ฝ๋๋ฅผ ์ฝ์ด๋ณด๋ฉด
- ๋ฌธ์ ๋ฅผ ์ ์ดํดํ๋์ง(1), ํ์ด๋ฒ์ด ์์ ํ์ง(2), ๊ฒํ (3, 4)๋ ํ๋์ง ์ ์ ์๋ค.
- ์๊ฐ์์ ์ ์ถ๊ธฐ๋ก
- ์ ์ถํ ๊ธฐ๋ก์ด ์๋ค๋ ๊ฒ์
- 0์
- 0์ ์ ๋ฐ์ ๊ฒฝ์ฐ๋
- ์์ ๋ง ๋๋ ค๋ณด๊ณ ์ ์ถ์ ํด๋ดค์ ๊ฐ๋ฅ์ฑ์ด ๋๋ค.
- ๋ฌธ์ ๋ฅผ ์๊ธฐ๋๋ฆ๋๋ก ์ดํดํ๊ณ (1), ์ฝ๋๊ฐ ๊ตฌํ(5)๋ ์ํฉ์ด๋ค. (ํ์ด๋ฒ์ด ์์ ํ์ง(2), ๊ฒํ (3, 4)๋ ํ๋์ง ๋ชจ๋ฅธ๋ค)
- 0์ ~ 90์
- ์๊ฐ์ด๊ณผ์ ๊ฒฝ์ฐ๋
- ์๊ฐ ๋ณต์ก๋(4) ๊ณ์ฐ์ด ์๋ชป๋์๊ฑฐ๋, ๊ณ์ฐ์ ํ ์ค ๋ชจ๋ฅผ ์ ์๋ค.
- ๋ฉ๋ชจ๋ฆฌ์ด๊ณผ์ ๊ฒฝ์ฐ๋
- ๋ฐฐ์ด์ ํฌ๊ธฐ๋ฅผ ๋๋ฌด ํฌ๊ฒ ์ก์๊ฑฐ๋(ํ, ์ ์ ๋ฉ๋ชจ๋ฆฌ ํฉ์ณ์ย 256MBย ์ด๊ณผ(์ ์ญ๋ณ์), ์คํ ๋ฉ๋ชจ๋ฆฌย 1MBย ์ด๊ณผ(main ๋ด์ ๋ณ์)), ์ฌ๊ท๊ฐ ๋๋ฌด ๋ง์ด ๋๋ค(ํจ์ ์ฝ์คํ ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ).
- ๋ฐํ์์๋ฌ์ ๊ฒฝ์ฐ๋
- ์ฃผ๋ก ๋ฐฐ์ด indexing์ด ์๋ชป๋์์๋ ๋ฐ์ํ๊ณ , ์ํ ๋ฌธ์ ์ ๊ฒฝ์ฐ 0์ผ๋ก ๋๋ ๊ฒฝ์ฐ ๋ฐ์ํ๋ค.
- ๋ฐฐ์ด ์ต๋ ํฌ๊ธฐ(4)๋ฅผ ์ฃผ๋ก ์๋ชป ์ค์ ํ๋ค.
- ์ด์ธ์ ๊ฒฝ์ฐ ๋ค์ํ ์ํฉ์
- ๋ฌธ์ ํด๊ฒฐ์ ์ฐจ ์ค 5, 4, 3, 2, 1 ์ค์ ์ด๋ ๊ฒ์ด ์๋ชป๋์๋์ง ํ์
ํด์ผํ๋ค.
- 91~99์
- 91~99์ ์ ๋ฐ์ ๊ฒฝ์ฐ๋
- ์์ผ๋ก ํด๋ด๋ ๋ฐ๊ฒฌํ์ง ๋ชปํ ํ๋ฅ ์ด ๋๋ค.
- ๋ฌธ์ ์ดํด๊ฐ ์๋ชป๋์ ํ๋ฅ ์ด ์๋ค.
- 100์
- 100์ ์ ๋ฐ์ ๊ฒฝ์ฐ๋
- 1, 2, 3, 4, 5, 6 ๋จ๊ณ๊ฐ ์ฒด๊ณ์ ์ผ๋ก ์๋ฆฝ๋์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํด์๋ค.
- ํด๋น ๋ฌธ์ ์ ๋ค์ํ ํ์ด๊ฐ ๊ถ๊ธํ ์ ์๋ค. ๋ํ ์์ ์ด ํ์ด๋ธ ํ์ด๊ฐ ๋ง๋์ง ๊ฒ์ฆํ๊ณ ์ถ์ดํ ์ ์๋ค.(์ฌ์ค ์ด ์ง๋ฌธ์ด ๋์์๋ ์๋๋ค. ๋ง์ฝ ์ง๋ฌธ์ด ๋์๋ค๋ฉด ์๊ฐ์์ ๋ฌธ์ ํด๊ฒฐ์ ์ฐจ ์คย 4, 3 ์ด ์ ์๋๋ ๊ฒ์ด๋ค.)
- ์ ์ถํ ์ฝ๋๋ฅผ ์ฝ์ด๋ณด๋ฉด
- 5, 4, 3, 2, 1 ์ค์ ์ด๋ ๊ฒ์ด ์๋ชป๋์๋์ง ํ์
ํ ์ ์๋ค.
- ๊ฐ ์๊ฐ์ ๋ง๋ค ๋์ฌ ์ง๋ฌธ์ ์์ธกํด์ ๋ฏธ๋ฆฌ ์ถฉ๋ถํ ์๊ฐํ๊ณ ๋ต๋ณ์ ์ค๋นํด๋๋ค.
- ์ฝ์นญ์ด ์์๋ ์ดํ ๋ฏธ๋ฆฌ ์์ธกํ ์ง๋ฌธ์ ๋ํ ๋ต๋ณ์ ์๊ฐ์์ด ๋ฌผ์ด๋ณด๊ธฐ๋ ์ ์ ์ฝ์น๊ฐ ๋จผ์ ์ฃผ๋ ๊ฒ์ด ์๋ ์๊ฐ์์ด ๋ฌผ์ด๋ดค์๋ ์ฝ์น๊ฐ ์ง๋ฌธ์ ๋ํ ๋ต๋ณ์ ์ ์ ํ๊ฒ ํด์ค์ผํ๋ค.
- ๋ง์ฝ ์์ธกํ ์ง๋ฌธ์ด ๋์๋ค๋ฉด ๋ฏธ๋ฆฌ ์๊ฐํด๋ ๋ต๋ณ์ ๋ง์ด๋ ๊ทธ๋ฆผ, ๊ธ๋ก ํํํ๋ฉด ๋๋ค. ์๋๋ผ๋ฉด ๋ฃ๊ณ ๋ฐ๋ก ์๊ฐํด๋ด์ผํ๋ค.
- ์๋ฅผ ๋ค์ด, ์๊ฐ์์ด ๊ถ๊ธํ ๋ฌธ์ (a, b, c)์ ๋ํ ์ค๋นํ ์ง๋ฌธ(x, y, z)๊ฐ ์๊ณ ์ฝ์น๊ฐ ์์ธกํ ๋ฌธ์ (a, b, c, d, e)์ ๋ํ ์ง๋ฌธ(x, y, w, o, p)์ ๋ํ ๋ต๋ณ(i, j, k)๊ฐ ์๋ค๋ฉด
- ์๊ฐ์์ด ๋ฌธ์ a ์ ๋ํ x ์ง๋ฌธ, ๋ฌธ์ b ์ ๋ํ y ์ง๋ฌธ, ๋ฌธ์ c ์ ๋ํ z ์ง๋ฌธ์ ํ๋ค๋ฉด
- ์ฝ์น๋ ๋ฌธ์ a, b ์ง๋ฌธ x, y ์ ๋ํด์๋ ์ค๋น๋ ์ง์ด ๋์ ๋ต๋ณ(i, j)์ ์ ๊ณตํ ๊ฒ์ด๊ณ , ๋ฌธ์ c ์ ๋ํ ์ง๋ฌธ z ์ ๋ํด์๋ ๋ฐ๋ก ์๊ฐํด๋ธ ๋ต๋ณ์ ์ ๊ณตํ ๊ฒ์ด๋ค.
- ์ฌ๊ธฐ์ ์ฝ์น๊ฐ ์์ธกํ ๋ฌธ์ d, e ์ ๋ํด ์ง๋ฌธ์ด ์์ผ์ ์ง ์๊ฐ์์๊ฒ ์ฌ์ญค๋ด์ผ๋ก ํ ๋ฒ ์ฒดํฌ๋ฅผ ํ๊ณ ๋์ด๊ฐ๋ฉด ๊ด๋ฆฌ ๋ฐ๋ ๋๋์ ์ ๊ณตํ ์ ์๋ค.
- ์ด๋ ์ง๋ฌธ์ ๋ํ Default ๋ต๋ณ์ "์ด๋ป๊ฒ ํธ์
จ๋์?"(2)๊ฐ ์์์ด๋ค.
- "์ด๋ป๊ฒ ํธ์
จ๋์?" ์ ๋ํ ์๊ฐ์์ ๋ต๋ณ์ ํตํด ๋ฌธ์ ์ดํด๋ฅผ ์ ํ๋์ง(1), ํ์ด๋ฅผ ๋๋ฐ๋ก ๊ฐ๋ฐํ๋์ง(3, 4) ์ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค.
- ์ฝ์น๋ ์๊ฐ์์ ์ง๋ฌธ์ ํตํด ๋ฌธ์ ํด๊ฒฐ์ ์ฐจ 6๋จ๊ณ ์ค ์ด๋ ๋ถ๋ถ์ด ์ ์๋๋์ง ํ์
ํด์ผํ๋ค. ๋ํ, ์์ ์ด ์ด๋ ๋ถ๋ถ์ด ์ ์๋๋์ง ์ธ์ง์์ผ์ค์ผํ๋ค.
- 1๋จ๊ณ๋ฅผ ๋ชปํ๋ค
- ๋ฌธ์ ๊ฐ ์ดํด๋์ง์๋๋คย โ desc ์ค๋ช
ํด์ค๋ค.
- ๋ฌธ์ ์์ ๊ตฌํด์ผ๋๋๊ฒ ๋ฌด์์ธ์ง ๋ชจ๋ฅธ๋คย โ ๋ฌธ์ ๋ฅผ ์ฝ๊ณ ๊ตฌํด์ผํ๋ ๊ฐ์ ์ ์ํ๋ ๊ณผ์ ์ ๋ณด์ฌ์ค๋ค. ๋ฌธ์ ์ ์์ ์์ธํจ์ 0, 1 ๋ฐ์ ๋ชจ๋ฅด๋ ์ปดํจํฐ๊ฐ ์ดํดํ ์ ์๋์ง๋ก ํ๋ฉด ์ ๋นํ๋ค.(์ฝ๋๋ก ๋ด๊ฐ ์ปดํจํฐ์๊ฒ ์ค๋ช
ํ ์ ์๋์ง)
- ex) ๋ฌธ์ ์ ์ - ์์๋ฅผ ๊ตฌํ๋ผ
- ์ปดํจํฐ์๊ฒ ๋ฐ๋ก ์์๋ฅผ ๊ตฌํ๋ผ๊ณ ํ๋ฉด ์์๊ฐ ๋ญ์ง ๋ชจ๋ฅผ ๊ฒ์ด๋ค. ์ข ๋ ๋ช
ํํ๊ฒ ์จ์ผํ๋ค.
- ๊ทธ๋ ๋ค๋ฉด ์์๋ ๋ฌด์์ด๊ณ , ์ด๋ป๊ฒ ํ๋จํ ์ ์๋๊ฐ
- ์์ : ์ฝ์๊ฐ 1๊ณผ ์๊ธฐ ์์ ์ธ ์ซ์
- ๋ฌธ์ ์ฌ์ ์ - (์ฝ์๊ฐ 1๊ณผ ์๊ธฐ ์์ ์ธ ์ซ์)๋ฅผ ๊ตฌํ๋ผ
- ์ปดํจํฐ์๊ฒ ์ฝ์๋ฅผ ๊ตฌํ๋ผ๊ณ ํ๋ฉด ์ฝ์๊ฐ ๋ญ์ง ๋ชจ๋ฅธ๋ค.
- ์ฝ์ : ์ซ์ x ๊ฐ ์์๋ x ๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์ ๋๋ ๋จ์ด์ง๋ ์
- ๋ฌธ์ ์ฌ์ ์ - ((์ซ์ x ๊ฐ ์์๋ x ๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์ ๋๋ ๋จ์ด์ง๋ ์)๊ฐ 1๊ณผ ์๊ธฐ ์์ ์ธ ์ซ์)๋ฅผ ๊ตฌํ๋ผ
- ๋๋ ๋จ์ด์ง๋ ์๋ฅผ ์์ง ๋ชจ๋ฅธ๋ค.
- ๋๋ ๋จ์ด์ง๋ ์ : ๋๋ด์๋ ๋๋จธ์ง๊ฐ 0์ธ ์
- ๋ฌธ์ ์ฌ์ ์ - ((์ซ์ x ๊ฐ ์์๋ x ๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์ (๋๋ด์๋ ๋๋จธ์ง๊ฐ 0์ธ ์))๊ฐ 1๊ณผ ์๊ธฐ ์์ ์ธ ์ซ์)๋ฅผ ๊ตฌํ๋ผ
- ์ด์ ์ปดํจํฐ๊ฐ ์์๋ฃ๊ฒ ๋ด๊ฐ ์ค๋ช
ํ (์ฝ๋๋ก ํํํ ) ์ ์๋ค.
- 2๋จ๊ณ๋ฅผ ๋ชปํ๋ค
- ๋ฐฉ๋ฒ์ ๋ชป๋ ์ฌ๋ฆฐ๋คย โ ๋ฌธ์ ์ดํด๋ฅผ ํตํด ํ์ด๋ฒ์ ๊ฐ๋ฐํ๋ ๊ณผ์ ์ ๋ณด์ฌ์ค๋ค.
- ex)ย ((์ซ์ x ๊ฐ ์์๋ x ๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์ ๋๋ ๋จ์ด์ง๋ ์)๊ฐ 1๊ณผ ์๊ธฐ ์์ ์ธ ์ซ์)๋ฅผ ๊ตฌํ๋ผ
- ์ซ์ x ๊ฐ ์์๋ x ๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์ ๋๋ ๋จ์ด์ง๋ ์๋ฅผ ์ด๋ป๊ฒ ๊ตฌํ ๊น?
- x ๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์ ์๋ฅผ ์์๋ด์ผํ๋ค.ย โ for(int i=0;i<x;i++) ๋ก ๋ฐ๋ก ๋์ค๋ฉด ์ ๋ง ์ข๊ฒ ์ง๋ง ํ์ค์ ๊ทธ๋ ์ง ์๋ค.
- ๋๋ ๋จ์ด์ง๋ ์ย โ ๋๋จธ์ง๊ฐ 0์ด์ฌ์ผ ํ๋ค(๋ฌธ์ ์ดํด๋ฅผ ์์ ํ ํ์ง ์์๋ ์ฌ๊ธฐ์ ๋ค์ ์ ์ํด ๋ณผ ๊ธฐํ๊ฐ ์๋ค) โย % ๋ฅผ ์ด์ฉํ๋คย โ x%i == 0
- ...
- ์ด๋ ค์ด ๋ฐฉ๋ฒ์ผ๋ก ๋ฌธ์ ๋ฅผ ํผ๋คย โ ์ผ๋จ ๊ทธ ๋ฐฉ๋ฒ์ผ๋ก ํ๊ณ์ ์ ๋๋ฌํ๊ฒ ํ๋ค. ๊ทธ ์ดํ ์ฌ๋ฌ ๋ค์ํ ๋ฐฉ๋ฒ์ ์๊ฐ์์ผ์ฃผ๊ณ , ๊ทธ ์ค ์ฌ์ด ๊ฒ์ ์ ํํ๋๋ก ๋ง๋ ๋ค.
- 3๋จ๊ณ๋ฅผ ๋ชปํ๋ค
- ๋ณดํต ๋ฌธ์ ์ดํด๊ฐ ๋ช
ํํ์ง ์๋ค.ย โ ๋ฌธ์ ์ดํดํ๋ ๊ณผ์ ์ ๋ณด์ฌ์ค๋ค. (๋ฌธ์ ์์ ๋ฐ์ํ ์ ์๋ ์ ์ฒด ์ํฉ์ ๋ ์ฌ๋ฆฌ๋ ์ฐ์ต)
- 4๋จ๊ณ๋ฅผ ๋ชปํ๋ค
- N ์ ํ์ ๊ฒํ ํ์ง ๋ชปํ๋ค โ ๋ฌธ์ ๋ฅผ ์ ์ฝ๋๋ก ์ง์ ํ๋ค.
- ์๊ฐ๋ณต์ก๋๋ฅผ ๋ชป๊ตฌํ๊ฒ ๋คย โ ๊ตฌํ๋ ๋ฐฉ๋ฒ์ ์๋ ค์ค๋ค.
- ์๊ฐ๋ณต์ก๋๋ฅผ ๊ตฌํ์ผ๋ ํ๋ ธ๋คย โ ๋ง๋ ๋ณต์ก๋๋ฅผ ๊ตฌํด์ค๋ค. ๊ตฌํ๋ ๋ฐฉ๋ฒ์ ์๋ ค์ค๋ค.
- ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผํ๋คย โ main ๋ด์์ ๋ณดํต int ํ์ผ๋ก 1,000,000(1๋ฐฑ๋ง)๊น์ง ํ ๋น ๊ฐ๋ฅํ๊ณ ์๋ ค์ค๋ค. (int data[100000] or int data[1000][1000]), ๊ทธ๋ณด๋ค ํฐ ๋ฐฐ์ด์ ์ ์ธํ๊ณ ์ถ์ ๊ฒฝ์ฐ ์ ์ญ๋ณ์๋ก ์ ์ธํ๋ฉด ๋ ์๋ ์์ง๋ง ๊ฑฐ๊ธฐ์๋ ๋๋ฌด ํฌ๋ฉด ๋ฐฐ์ด์ ์ฌ์ฉํ๋ฉด ์๋๋ ๋ฌธ์ ๋ผ๊ณ ์ธ๊ธํ๋ค.
- 5๋จ๊ณ๋ฅผ ๋ชปํ๋ค
- ์ฝ๋๋ก ๋ชป์ง๊ฒ ๋ค
- ๋ง๋ ํ์ด๋ฅผ ๋ฉ๋ชจ์ง์ ์ ์ผ๋ฉด์ ํ์ง ์์๋ค โ ๊ธ๋ก ์ฐ๋ฉด์ ๋ฌธ์ ๋ฅผ ํ๊ฒ ๋ง๋ ๋ค.
- ๋ง๋ ํ์ด๋ฅผ ๋ฉ๋ชจ์ง์ ์ ์ผ๋ฉด์ ํ๋๋ฐ ๋ณด์ํ๋ ํ์ด๋ฒ์ด ํผ์ง ํผ์งํ๋ค โ ์ข ๋ ์์ธํ๊ฒ ์ ์ ์ ์๋๋ก ํ๋ค. โย ย ํ๊ธ๋ก ์ ์ ํ์ด ๊ณผ์ 1, 2, 3, 4 ๊ฐ ๊ฐ๊ฐ ์ฝ๋ ํ ์ค๋ก ํํ๋ ์ ์์ ๋๊น์ง ์์ธํ๊ฒ ์ด๋ค.
- ๋ง๋ ํ์ด ์ค ํน์ ๋จ๊ณ๋ฅผ ๋ชป ์ง๊ฒ ๋คย โ ๋ค์ํ ๊ตฌํ ๋ฐฉ๋ฒ์ ์๋ ค์ค๋ค.
- ๋ง๋ ํ์ด๋ฒ์ด ๋ง๋ค โ ํ๋ก๊ทธ๋๋ฐ ๋ฌธ์ ํด๊ฒฐ ํ
ํฌ๋์ ์๋ ค์ค๋ค. ex. 2์ฐจ์ ๋ฐฐ์ด padding, counting array
- 6๋จ๊ณ๋ฅผ ๋ชปํ๋ค
- ๋๋ฒ๊น
์ ํ ์ค ๋ชจ๋ฅธ๋ค.ย โ ๋๋ฒ๊น
์ ์๋ ค์ค๋ค.
- ๋๋ฒ๊น
์ ํ ์ค ๋ชจ๋ฅด์ง๋ง ์๊ธฐ๊ฐ ๋ง๋ ์์ ๋ฅผ ๋ฃ์ด๋ดค๋๋ฐ ๋ค ๋ง๋ค.ย โ ๋๋ฒ๊น
์ ์๋ ค์ฃผ๊ณ ,ย ๋ฌธ์ ์์ ๊ตฌํด์ผ๋๋ ๊ฐ์ด ๋์ฌ ์ ์๋ ๋ชจ๋ ์ํฉ๊ณ ๋ ค๊ฐ ๋์ง์์๋ค๊ณ ์๋ ค์ค๋ค.
- ๋๋ฒ๊น
์ ํ ์ค ์์ง๋ง ์๊ธฐ๊ฐ ๋ง๋ ์์ ๋ฅผ ์๋ฃ์ด๋ดค๋ค.ย โ ์์ ๋๋ ค๋ณด๋ผ๊ณ ํ๋ค;
- ๋๋ฒ๊น
์ ํ ์ค ์๊ณ ์๊ธฐ๊ฐ ๋ง๋ ์์ ๋ฅผ ๋ฃ์ด๋ดค๋๋ฐ ๋ค ๋ง๋ค.ย โย ๋ฌธ์ ์์ ๊ตฌํด์ผ๋๋ ๊ฐ์ด ๋์ฌ ์ ์๋ ๋ชจ๋ ์ํฉ๊ณ ๋ ค๊ฐ ๋์ง์์๋ค๊ณ ์๋ ค์ค๋ค.
- ์์ธ๊ฐ ๋ฐ์ํ๋คย โ ํ์ด๋ฒ์ ๋ง๋ค๋ brute force ๋ถํฐ ์๊ฐํ์ง ์์๋ค. ๋๋ ๋ฌธ์ ์์ ๊ตฌํด์ผ๋๋ ๊ฐ์ด ๋์ฌ ์ ์๋ ๋ชจ๋ ์ํฉ๊ณ ๋ ค๊ฐ ๋์ง์์๋ค.
- ๋ชจ๋ ์ํฉ์ ๊ณ ๋ คํ๋ ๋ชจ์ต์ ๋ณด์ฌ์ค๋ค.
- ์์ธ๋ฅผ ์ค์ ์ค์ค๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ฒ ๋ง๋ ๋ค. (๋ฌธ์ ์ดํด๋ฅผ ์ค์ค๋ก ์๋ชปํ๋ค๊ณ ๊นจ๋ซ๋๋ค)
- ์๊ณ ๋ฆฌ์ฆ์ ์๋ ค์ค๋ค๋ ๊ฒ์
- Brute-force๋ก ์ค๊ณํ ํ์ด๋ฒ์์ ๋ ํจ์จ์ ์ผ๋ก ๋ง๋ค ์ ์๋ ๋ถ๋ถ์ ์ฐพ์์ ํด๋น ๋ถ๋ถ์ ์๋ฃ๊ตฌ์กฐ๋ ์๊ณ ๋ฆฌ์ฆ์ ํตํด ์๊ฐ๋ณต์ก๋๋ฅผ ์ค์ด๋ ํ์๋ฅผ ์๋ ค์ฃผ๋ ๊ฒ์ด๋ค.
- ์ฃผ์ด์ง ์ด๋ ํ ์ํฉ์ ๋ํ ์ ํด์ง ํ์ด๋ฒ์ ์๋ ค์ฃผ๋ ๊ฒ์ด๋ค.
-
์ง๋ ๊ด๋ฆฌ
- ์ง๋ ๊ด๋ฆฌ๋ ๋ค์ํ๊ณ ๋ง์ ์ง์ ์๋ต์ ์ ๋ํ๊ธฐ ์ํ ๋๊ตฌ๋ก ์ฐ์ผ ์ ์๊ณ , ์ต๋ํ ์งง์ ์๊ฐ์ ๋ค์ํ ์๊ณ ๋ฆฌ์ฆ์ ์ ํ ์ ์๋๋ก ํ๊ธฐ ์ํจ์ด๋ค.
- ๋ํ, ์๊ฐ์์ด ํ์ต์ ์ผ๋ก ๋์์ด๋๋ ์์๋ก ํ ์ ์๋๋ก ์ฝ์น๊ฐ ์ ๋ํ๊ธฐ ์ํจ์ด๋ค.
- ์๊ฐ์์ด ๋ค์ํ ์ง๋ฌธ์ ๊ฐ์ง๊ณ ์ฌ ์ ์๋๋ก ์ต๋ํ ๋ง์ ๋ฌธ์ ๋ฅผ ํ ์ ์์ ๋งํผ ํ์ด์ค๋๋ก ๋งํ๋ค.(์ง๋ฌธ์ ๋ํ ๋ง์กฑ๋ ๋์ ๋ต๋ณ์ ์ค ์ ์๋ ์ํฉ + ๋ชจ๋ ์ง๋ฌธ์ ๋ํ ๋ต์ ์ค ์ ์๋ ์ํฉ์ด๋ผ๋ฉด ํด์๋ ์๋๋ค.)
- ์ฃผ์ด์ง ์ปจํ
์ธ (๋ฌธ์ , ์์)์ ํตํด ๋ฌธ์ ํด๊ฒฐ๋ฅ๋ ฅ ์ค ์ด๋ ๊ฒ์ ๊ฒ์ฆํ ์ ์์์ง๋ฅผ ๊ณ ๋ คํ์ฌ ์๊ฐ์์ด ์ด๋์ ๋๋ก ๋ฌธ์ ํด๊ฒฐ๋ฅ๋ ฅ์ ๊ฐ์ท๋์ง ์ ๊ฒ ํด๋ณผ ์ ์๋ ๊ฒ์ฆ ์๋จ์ผ๋ก ์ด์ฉํ๊ฒ ๋๋ค. ex) k๋ฒ์งธ ํฐ ์ ์ฐพ๊ธฐ - ๋ฌธ์ ์กฐ๊ฑด ํ์
ํ ๊ฒ์ฆ(4), ์๊ฐ๋ณต์ก๋ ๊ณ์ฐ(4)
๊ณ ์ค๊ธ ์ฝ์น๊ฐ ๋์ด๊ฐ๋ ๊ณผ์
์ง์ ์๋ต์ ์งํํ ๋ ์ผ์ด๋๋ ์ํฉ์ ์๊ฒ ๋๋ ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
- ์ง๋ฌธ์ ํด์ผ๋๋ ์ํฉ์ธ์ง ๋ชจ๋ฅด๊ฒ ๋ค.
- ์ง๋ฌธ์ ํด์ผ๋๋ ์ํฉ์ธ์ง๋ ์๊ฒ ์ผ๋ ์ง๋ฌธ์ ๋ญ ํด์ผํ ์ง ๋ชจ๋ฅด๊ฒ ๋ค.
- ์ง๋ฌธ์ ํ์ผ๋ ๋ต๋ณ์ด ๋ถ์ ์ ํ๋ค.
- ์ง๋ฌธ์ ํ๊ณ ๋ต๋ณ์ด ์ ์ ํ์ผ๋ ์ดํดํ์ง ๋ชปํ๋ค.
- ์ง๋ฌธ์ ํ๊ณ ๋ต๋ณ๋ ์ ์ ํ๊ณ ์ดํด๊น์ง ํ์ผ๋ ์ด๋ป๊ฒ ํ ์ง ๋ชจ๋ฅด๊ฒ ๋ค.
์์ ์์ ํ ๋ฐฉ์์ผ๋ก ์๋ฌ์ด ๋ ์ฝ์น๋ ๋์ ํ๋ฅ ๋ก 3, 4, 5์ ๋ํ ์ํฉ ๋์์ด ๊ฐ๋ฅํ ๊ฒ์ด๋ค.
์๊ฐ์์๊ฒ ์ข ๋ ๋ง์กฑ๋, ์ง ๋์ ์๋น์ค๋ฅผ ์ ๊ณตํ๊ธฐ ์ํด์๋ ์๊ฐ์์ด ๊ณ ๋ฏผํ๋ ์๊ฐ ์ต๋ํ ํจ์จ์ ์ผ๋ก ์ฌ์ฉํ๊ฒ ๋ง๋๋ ๊ฒ์ด๋ค.
- ๋ง์ฝ 3์๊ฐ ๊ณ ๋ฏผํด์ ์๊ฐ์ด ์๋ ์ค๋ฅด๊ณ , 10์๊ฐ ๊ณ ๋ฏผํด์ ์๊ฐ์ด ์๋ ์ค๋ฅด๋๊ฒ ๋๊ฐ๋ค๋ฉด ์๊ฐ์ ๊ฐ์ฅ ํจ์จ์ ์ผ๋ก ์ฐ๋ ๋ฐฉ๋ฒ์ 3์๊ฐ๋ง ๊ณ ๋ฏผํด๋ณด๋ ๊ฒ์ด๋ค. (ํ๋ผ๋งคํธ๋ฆญ ์์น์ ๋์ผํ ๋ก์ง์ด๋ค)
- ์๊ฐ์ ๊ฐ๋ณ์ Minimum ๊ณ ๋ฏผ ์๊ฐ์ ์์๋ด์ ์๊ฐ์์ ์์คํ ์๊ฐ์ ์ต๋ํ ํจ์จ์ ์ผ๋ก ์ฌ์ฉํ ์ ์๋๋ก ๋์์ค์ผํ๋ค.
- ์ด๋ ์ ์ํฉ ์ค 1, 2 ์ ํด๋นํ๋ ์ํฉ์ธ๋ฐ, ์ฝ์น๊ฐ ํ์ฌ๋ก๋ ๊ฐ์ผ๋ก ํ์
ํ์ฌ ์ฝ์นญ์ด ์งํ๋์ด์ผํ๋ค.
- ๋ง์ฝ ์๊ฐ์ ๊ฐ์ธ์ Minimum ๊ณ ๋ฏผ ์๊ฐ์ ์์๋๋ค๋ฉด ๋ค์๊ณผ ๊ฐ์ ํ์๊ฐ ๊ฐ๋ฅํด์ง๋ค.
- ์๋ฅผ ๋ค์ด, A ์๊ฐ์์ ์ต์ ๊ณ ๋ฏผ ์๊ฐ์ 10๋ถ์ด๋ค. ๊ทธ๋ ๋ค๋ฉด ํด๋น ์๊ฐ์์๊ฒ ๊ณ ๋ฏผํด๋ณผ ์ ์๋ ์ง๋ฌธ์ ๋์ง ๋ค์, ํด๋น ์ง๋ฌธ์ ๋ํ ๋ต๋ณ์ ์๊ฐํ๋๋ฐ์ 10๋ถ์ ์ฃผ๊ณ 10๋ถ ๋ค์ ๋ค์ ๋ฌผ์ด๋ณด๋ ๊ฒ์ด๋ค.
- ๋ง์ฝ ์๊ฐ์ด ๋ ํ์ํ๋ค๊ณ ๋ง์ ํ๋ค๋ฉด ์๊ฐ์ ์ข ๋ ์ฃผ๊ณ , ์ฃผ์ด์ง ์๊ฐ๋ด์ ์๊ฐ์ ๋ชปํ๋ค๋ฉด ์๋ ค์ฃผ๊ณ ๋ค์ ๊ณ ๋ฏผ์ ํ๊ฒ ๋ง๋ ๋ค.
๋ํ 3, 4, 5 ์ ๋ํ ์ฌ์ธต์ ์ธ ์ํฉ ๋ถ์์ด ๋์ด์ ธ์ผ ํ๋ค.
- ์๋ฅผ ๋ค๋ฉด, ์๊ฐ์์ด ์ง๋ฌธ์ ๋ํด ์ ๋๋ก ์ดํดํ๋์ง ๋ชปํ๋์ง ์ ํํ๊ฒ ํ์
ํ ์ ์์ด์ผํ๋ค.
- ๋ต๋ณ์ ๋ฃ๊ณ ์ดํดํ ์ฒ ํ ์๋ ์๊ณ , ์ดํดํ ์ค ์ฐฉ๊ฐํ์ ์๋ ์๋ค.
- ์ง์์ ์ธ ์ง์์๋ต ๊ณผ์ ์ ํตํด ์ ํํ ์ดํด ์์ค์ ์์๋ด์ผํ๋ค.
์ฝ์น ๋ ๋ฒจ
๋ต์ ์๋ ค์ค๋ค (์ ๊ธ)
์ง๋ฌธ์ ๋ํ ๋ต์ ๋ฐ๋ก ์๋ ค์ฃผ๋๋ก ๋ต๋ณ์ด ๊ฐ๋ฅํ๋ค.
์ง๋ฌธ์ ๋ํ ๋ต์ด ๋ฐ๋ก ์๊ฐ๋ ์ ์๊ฒ ๋ต๋ณ์ด ๊ฐ๋ฅํ๋ค.
์ง๋ฌธ์ ๋ํ ๋ต์ด ๊ณ ๋ฏผํด์ ์๊ฐ๋ ์ ์๊ฒ ๋ต๋ณ์ด ๊ฐ๋ฅํ๋ค.
๋ฐฉ๋ฒ์ ์๋ ค์ค๋ค (๊ณ ๊ธ)
๋ฌผ๊ณ ๊ธฐ๋ฅผ ์ก์์ฃผ๋ ์ก๋ ๋ฐฉ๋ฒ์ ์๋ ค์ฃผ๋ ์ฐจ์ด์ธ ๊ฒ ๊ฐ๋ค.