์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค ๋ฌธ์ ํ์ด
๊ทธ๋ฆฌ๋(Greedy) ์๊ณ ๋ฆฌ์ฆ์ ๋จ์ํ์ง๋ง ๊ฐ๋ ฅํ ๋ฌธ์ ํด๊ฒฐ ๋ฐฉ๋ฒ์ด๋ค. 'ํ์๋ฒ'์ผ๋ก๋ ์๋ ค์ง ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ด๋ ํ ๋ฌธ์ ๊ฐ ์์ ๋ ๋จ์ ๋ฌด์ํ๊ฒ, ํ์์ ์ผ๋ก ๋ฌธ์ ๋ฅผ ํธ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ฌ๊ธฐ์ ํ์์ ์ด๋ผ๋ ๋ง์ 'ํ์ฌ ์ํฉ์์ ์ง๊ธ ๋น์ฅ ์ข์ ๊ฒ๋ง ๊ณ ๋ฅด๋ ๋ฐฉ๋ฒ'์
๋น์ ์ ์์์ ์ ๊ณ์ฐ์ ๋์์ฃผ๋ ์ ์์ด๋ค. ์นด์ดํฐ์๋ ๊ฑฐ์ค๋ฆ๋์ผ๋ก ์ฌ์ฉํ 500์, 100์, 50์, 10์์ง๋ฆฌ ๋์ ์ด ๋ฌดํํ ์กด์ฌํ๋ค๊ณ ๊ฐ์ ํ๋ค. ์๋์๊ฒ ๊ฑฐ์ฌ๋ฌ ์ค์ผ ํ ๋์ด N์์ผ ๋ ๊ฑฐ์ฌ๋ฌ ์ค์ผ ํ ๋์ ์ ์ต์ ๊ฐ์๋ฅผ ๊ตฌํ๋ผ. ๋จ, ๊ฑฐ์ฌ๋ฌ ์ค์ผ ํ ๋์ ํญ์
'ํฐ ์์ ๋ฒ์น'์ ์ผ๋ฐ์ ์ผ๋ก ํต๊ณ ๋ถ์ผ์์ ๋ค๋ฃจ์ด์ง๋ ๋ด์ฉ์ด์ง๋ง ๋๋น์ด๋ ๋ณธ์ธ๋ง์ ๋ฐฉ์์ผ๋ก ๋ค๋ฅด๊ฒ ์ฌ์ฉํ๊ณ ์๋ค. ๋๋น์ด์ ํฐ ์์ ๋ฒ์น์ ๋ค์ํ ์๋ก ์ด๋ฃจ์ด์ง ๋ฐฐ์ด์ด ์์ ๋ ์ฃผ์ด์ง ์๋ค์ M๋ฒ ๋ํ์ฌ ๊ฐ์ฅ ํฐ ์๋ฅผ ๋ง๋๋ ๋ฒ์น์ด๋ค. ๋จ, ๋ฐฐ์ด์ ํน์ ํ ์ธ๋ฑ์ค(๋ฒํธ
์ซ์ ์นด๋ ๊ฒ์์ ์ฌ๋ฌ ๊ฐ์ ์ซ์ ์นด๋ ์ค์์ ๊ฐ์ฅ ๋์ ์ซ์์๊ฐ ์ฐ์ธ ์นด๋ ํ ์ฅ์ ๋ฝ๋ ๊ฒ์์ด๋ค. ๋จ, ๊ฒ์์ ๋ฃฐ์ ์งํค๋ฉฐ ์นด๋๋ฅผ ๋ฝ์์ผ ํ๊ณ ๋ฃฐ์ ๋ค์๊ณผ ๊ฐ๋ค.1\. ์ซ์๊ฐ ์ฐ์ธ ์นด๋๋ค์ด N X M ํํ๋ก ๋์ฌ ์๋ค. ์ด๋ N์ ํ์ ๊ฐ์๋ฅผ ์๋ฏธํ๋ฉฐ, M์ ์ด์
์ด๋ ํ ์ N์ด 1์ด ๋ ๋๊น์ง ๋ค์์ ๋ ๊ณผ์ ์ค ํ๋๋ฅผ ๋ฐ๋ณต์ ์ผ๋ก ์ ํํ์ฌ ์ํํ๋ ค๊ณ ํ๋ค. ๋จ, ๋ ๋ฒ์งธ ์ฐ์ฐ์ N์ด K๋ก ๋๋์ด๋จ์ด์ง ๋๋ง ์ ํํ ์ ์๋ค. 1\. N์์ 1์ ๋บ๋ค.2\. N์ K๋ก ๋๋๋ค.์๋ฅผ ๋ค์ด N์ด 17, K๊ฐ 4๋ผ๊ณ ๊ฐ์ ํ์. ์ด๋ 1
ํ ๋ง์์ ๋ชจํ๊ฐ๊ฐ N๋ช ์์ต๋๋ค. ๋ชจํ๊ฐ ๊ธธ๋์์๋ N๋ช ์ ๋ชจํ๊ฐ๋ฅผ ๋์์ผ๋ก '๊ณตํฌ๋'๋ฅผ ์ธก์ ํ๋๋ฐ, '๊ณตํฌ๋'๊ฐ ๋์ ๋ชจํ๊ฐ๋ ์ฝ๊ฒ ๊ณตํฌ๋ฅผ ๋๊ปด ์ํ ์ํฉ์์ ์ ๋๋ก ๋์ฒํ ๋ฅ๋ ฅ์ด ๋จ์ด์ง๋๋ค. ๋ชจํ๊ฐ ๊ธธ๋์ฅ์ธ ๋๋น์ด๋ ๋ชจํ๊ฐ ๊ทธ๋ฃน์ ์์ ํ๊ฒ ๊ตฌ์ฑํ๊ณ ์ ๊ณตํฌ๋๊ฐ X์ธ
๊ฐ ์๋ฆฌ๊ฐ ์ซ์(0๋ถํฐ 9)๋ก๋ง ์ด๋ฃจ์ด์ง ๋ฌธ์์ด S๊ฐ ์ฃผ์ด์ก์ ๋, ์ผ์ชฝ๋ถํฐ ์ค๋ฅธ์ชฝ์ผ๋ก ํ๋์ฉ ๋ชจ๋ ์ซ์๋ฅผ ํ์ธํ๋ฉฐ ์ซ์ ์ฌ์ด์ 'x' ํน์ '+' ์ฐ์ฐ์๋ฅผ ๋ฃ์ด ๊ฒฐ๊ณผ์ ์ผ๋ก ๋ง๋ค์ด์ง ์ ์๋ ๊ฐ์ฅ ํฐ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์. ๋จ, +๋ณด๋ค x๋ฅผ ๋จผ์ ๊ณ์ฐํ๋
๋ค์์ด๋ 0๊ณผ 1๋ก๋ง ์ด๋ฃจ์ด์ง ๋ฌธ์์ด S๋ฅผ ๊ฐ์ง๊ณ ์์ต๋๋ค. ๋ค์์ด๋ ์ด ๋ฌธ์์ด S์ ์๋ ๋ชจ๋ ์ซ์๋ฅผ ์ ๋ถ ๊ฐ๊ฒ ๋ง๋ค๋ ค๊ณ ํฉ๋๋ค. ๋ค์์ด๊ฐ ํ ์ ์๋ ํ๋์ S์์ ์ฐ์๋ ํ๋ ์ด์์ ์ซ์๋ฅผ ์ก๊ณ ๋ชจ๋ ๋ค์ง๋ ๊ฒ์ ๋๋ค. ๋ค์ง๋ ๊ฒ์ 1์ 0์ผ๋ก, 0์ 1๋ก ๋ฐ๊พธ๋
๋๋ค ํธ์์ ์ ์ฃผ์ธ์ธ ๋๋น์ด๋ N๊ฐ์ ๋์ ์ ๊ฐ์ง๊ณ ์์ต๋๋ค. ์ด๋ N๊ฐ์ ๋์ ์ ์ด์ฉํ์ฌ ๋ง๋ค ์ ์๋ ์์ ์ ์ ๊ธ์ก ์ค ์ต์๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์.์๋ฅผ ๋ค์ด, N=5์ด๊ณ , ๊ฐ ๋์ ์ด ๊ฐ๊ฐ 3์, 2์, 1์, 1์, 9์์ง๋ฆฌ(ํํ ๋จ์) ๋์ ์ด๋ผ๊ณ ๊ฐ์
A,B ๋ ์ฌ๋์ด ๋ณผ๋ง์ ์น๊ณ ์์ต๋๋ค. ๋ ์ฌ๋์ ์๋ก ๋ฌด๊ฒ๊ฐ ๋ค๋ฅธ ๋ณผ๋ง๊ณต์ ๊ณ ๋ฅด๋ ค๊ณ ํฉ๋๋ค. ๋ณผ๋ง๊ณต์ ์ด N๊ฐ๊ฐ ์์ผ๋ฉฐ ๊ฐ ๋ณผ๋ง๊ณต๋ง๋ค ๋ฌด๊ฒ๊ฐ ์ ํ ์๊ณ , ๊ณต์ ๋ฒํธ๋ 1๋ฒ๋ถํฐ ์์๋๋ก ๋ถ์ฌ๋ฉ๋๋ค. ๋ํ ๊ฐ์ ๋ฌด๊ฒ์ ๊ณต์ด ์ฌ๋ฌ ๊ฐ ์์ ์ ์์ง๋ง, ์๋ก ๋ค๋ฅธ ๊ณต์ผ๋ก
๊ฐ๋ ๐ ์ฝ๋ฉ ํ ์คํธ์์ ๊ตฌํ(Implementation)์ด๋ '๋จธ๋ฆฟ์์ ์๋ ์๊ณ ๋ฆฌ์ฆ์ ์์ค์ฝ๋๋ก ๋ฐ๊พธ๋ ๊ณผ์ '์ด๋ค. ์ด๋ค ๋ฌธ์ ๋ฅผ ํ๋ ๊ฐ์ ์์ค์ฝ๋๋ฅผ ์์ฑํ๋ ๊ณผ์ ์ ํ์์ด๋ฏ๋ก ๊ตฌํ ๋ฌธ์ ์ ํ์ ๋ชจ๋ ๋ฒ์์ ์ฝ๋ฉ ํ ์คํธ ๋ฌธ์ ์ ํ์ ํฌํจํ๋ ๊ฐ๋ ์ด๋ค. ๊ตฌํ์ ๋ํ์
์ฌํ๊ฐ A๋ NxN ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ๊ณต๊ฐ ์์ ์ ์๋ค. ์ด ๊ณต๊ฐ์ 1X1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๊ฐ์ฅ ์ผ์ชฝ ์ ์ขํ๋ (1,1)์ด๋ฉฐ, ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์๋ ์ขํ๋ (N,N)์ ํด๋นํ๋ค. ์ฌํ๊ฐ A๋ ์,ํ,์ข,์ฐ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ ์ ์์ผ๋ฉฐ, ์์ ์ขํ๋ ํญ์
์ ์ N์ด ์ ๋ ฅ๋๋ฉด 00์ 00๋ถ 00์ด๋ถํฐ N์ 59๋ถ 59์ด๊น์ง์ ๋ชจ๋ ์๊ฐ ์ค์์ 3์ด ํ๋๋ผ๋ ํฌํจ๋๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด 1์ ์ ๋ ฅํ์ ๋ ๋ค์์ 3์ด ํ๋๋ผ๋ ํฌํจ๋์ด ์์ผ๋ฏ๋ก ์ธ์ด์ผ ํ๋ ์๊ฐ์ด๋ค.00์ 00๋ถ 03์ด
ํ๋ณต ์๊ตญ์ ์์ค ์ ์์ ์ฒด์คํ๊ณผ ๊ฐ์ 8x8 ์ขํ ํ๋ฉด์ด๋ค. ์์ค ์ ์์ ํน์ ํ ํ ์นธ์ ๋์ดํธ๊ฐ ์ ์๋ค. ๋์ดํธ๋ ๋งค์ฐ ์ถฉ์ฑ์ค๋ฌ์ด ์ ํ๋ก์ ๋งค์ผ ๋ฌด์ ์ ์ฐ๋งํ๋ค. ๋์ดํธ๋ ๋ง์ ํ๊ณ ์๊ธฐ ๋๋ฌธ์ ์ด๋์ ํ ๋๋ L์ ํํ๋ก๋ง ์ด๋ํ ์ ์์ผ๋ฉฐ ์ ์ ๋ฐ์ผ๋ก๋ ๋๊ฐ
ํ๋ฏผ์ด๋ ๊ฒ์ ์บ๋ฆญํฐ๊ฐ ๋งต ์์์ ์์ง์ด๋ ์์คํ ์ ๊ฐ๋ฐ ์ค์ด๋ค. ์บ๋ฆญํฐ๊ฐ ์๋ ์ฅ์๋ 1x1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ์ผ๋ก ์ด๋ค์ง N x M ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ์ผ๋ก, ๊ฐ๊ฐ์ ์นธ์ ์ก์ง ๋๋ ๋ฐ๋ค์ด๋ค. ์บ๋ฆญํฐ๋ ๋์๋จ๋ถ ์ค ํ ๊ณณ์ ๋ฐ๋ผ๋ณธ๋ค.๋งต์ ๊ฐ ์นธ์ (A,B)๋ก ๋ํ๋ผ ์ ์๊ณ
๊ฒ์์ ์์๋ณต์ ์บ๋ฆญํฐ๋ ํ์ด๊ธฐ์ธ '๋ญํค ์คํธ๋ ์ดํธ' ๊ธฐ์ ์ด ์์ต๋๋ค. ์ด ๊ธฐ์ ์ ๋งค์ฐ ๊ฐ๋ ฅํ ๋์ ์ ๊ฒ์ ๋ด์์ ์ ์๊ฐ ํน์ ์กฐ๊ฑด์ ๋ง์กฑํ ๋๋ง ์ฌ์ฉํ ์ ์์ต๋๋ค. ํน์ ์กฐ๊ฑด์ด๋ ํ์ฌ ์บ๋ฆญํฐ์ ์ ์๋ฅผ N์ด๋ผ๊ณ ํ ๋ ์๋ฆฟ์๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ์ N์ ๋ฐ์ผ๋ก ๋๋์ด ์ผ์ชฝ
์ํ๋ฒณ ๋๋ฌธ์์ ์ซ์(0~9)๋ก๋ง ๊ตฌ์ฑ๋ ๋ฌธ์์ด์ด ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋๋ค. ์ด๋ ๋ชจ๋ ์ํ๋ฒณ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ์ด์ด์ ์ถ๋ ฅํ ๋ค์, ๊ทธ ๋ค์ ๋ชจ๋ ์ซ์๋ฅผ ๋ํ ๊ฐ์ ์ด์ด์ ์ถ๋ ฅํฉ๋๋ค. ์๋ฅผ ๋ค์ด K1KA5CB7์ด๋ผ๋ ๊ฐ์ด ๋ค์ด์ค๋ฉด ABCKK13์ ์ถ๋ ฅํฉ๋๋ค.์ฒซ์งธ ์ค์
'Dummy'๋ผ๋ ๋์ค ๊ฒ์์ด ์์ต๋๋ค. ์ด ๊ฒ์์๋ ๋ฑ์ด ๋์์ ๊ธฐ์ด ๋ค๋๋๋ฐ, ์ฌ๊ณผ๋ฅผ ๋จน์ผ๋ฉด ๋ฑ ๊ธธ์ด๊ฐ ๋์ด๋ฉ๋๋ค. ๋ฑ์ด ์ด๋ฆฌ์ ๋ฆฌ ๊ธฐ์ด ๋ค๋๋ค๊ฐ ๋ฒฝ ๋๋ ์๊ธฐ ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ๋ฉด ๊ฒ์์ด ๋๋ฉ๋๋ค. ๊ฒ์์ N x N ์ ์ฌ๊ฐ ๋ณด๋ ์์์ ์งํ๋๊ณ , ๋ช๋ช ์นธ์๋ ์ฌ๊ณผ๊ฐ
DFS/BFS์ ์์ ๊ผญ ํ์ํ ์๋ฃ๊ตฌ์กฐ ๊ธฐ์ด๋ถํฐ ์ ๋ฆฌํ๋ ค๊ณ ํ๋ค.ํ์์ด๋ <span style='background-color: ์๋ฃ๊ตฌ์กฐ๋ <span style='background-color: \* ์ฝ์ (Push): ๋ฐ์ดํฐ๋ฅผ ์ฝ์ ํ๋ค.์ญ์ (Pop): ๋ฐ์ด
N x M ํฌ๊ธฐ์ ์ผ์ ํ์ด ์๋ค. ๊ตฌ๋ฉ์ด ๋ซ๋ ค ์๋ ๋ถ๋ถ์ 0, ์นธ๋ง์ด๊ฐ ์กด์ฌํ๋ ๋ถ๋ถ์ 1๋ก ํ์๋๋ค. ๊ตฌ๋ฉ์ด ๋ซ๋ ค ์๋ ๋ถ๋ถ๋ผ๋ฆฌ ์,ํ,์ข,์ฐ ๋ถ์ด ์๋ ๊ฒฝ์ฐ ์๋ก ์ฐ๊ฒฐ๋์ด ์๋ ๊ฒ์ผ๋ก ๊ฐ์ฃผํ๋ค. ์ด๋ ์ผ์ ํ์ ๋ชจ์์ด ์ฃผ์ด์ก์ ๋ ์์ฑ๋๋ ์ด ์์ด์คํฌ๋ฆผ์ ๊ฐ์๋ฅผ
๋๋น์ด๋ N x M ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ ํํ์ ๋ฏธ๋ก์ ๊ฐํ ์๋ค. ๋ฏธ๋ก์๋ ์ฌ๋ฌ ๋ง๋ฆฌ์ ๊ดด๋ฌผ์ด ์์ด ์ด๋ฅผ ํผํด ํ์ถํด์ผ ํ๋ค. ๋๋น์ด์ ์์น๋ (1,1)์ด๊ณ ๋ฏธ๋ก์ ์ถ๊ตฌ๋ (N,M)์ ์์น์ ์กด์ฌํ๋ฉฐ ํ๋ฒ์ ํ ์นธ์ฉ ์ด๋ํ ์ ์๋ค. ์ด๋ ๊ดด๋ฌผ์ด ์๋ ๋ถ๋ถ์ 0์ผ๋ก, ๊ดด๋ฌผ
์ด๋ค ๋๋ผ์๋ 1 ~ N๋ฒ๊น์ง์ ๋์์ M๊ฐ์ ๋จ๋ฐฉํฅ ๋๋ก๊ฐ ์กด์ฌํฉ๋๋ค. ๋ชจ๋ ๋๋ก์ ๊ฑฐ๋ฆฌ๋ 1์ ๋๋ค. ์ด๋ ํน์ ํ ๋์ X๋ก๋ถํฐ ์ถ๋ฐํ์ฌ ๋๋ฌํ ์ ์๋ ๋ชจ๋ ๋์ ์ค์์, ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์ ํํ K์ธ ๋ชจ๋ ๋์์ ๋ฒํธ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์. ๋ํ ์ถ๋ฐ ๋์
์ธ์ฒด์ ์น๋ช ์ ์ธ ๋ฐ์ด๋ฌ์ค๋ฅผ ์ฐ๊ตฌํ๋ ์ฐ๊ตฌ์์์ ๋ฐ์ด๋ฌ์ค๊ฐ ์ ์ถ๋์์ต๋๋ค. ๋คํํ ๋ฐ์ด๋ฌ์ค๋ ์์ง ํผ์ง์ง ์์๊ณ , ๋ฐ์ด๋ฌ์ค์ ํ์ฐ์ ๋ง๊ธฐ ์ํด์ ์ฐ๊ตฌ์์ ๋ฒฝ์ ์ธ์ฐ๋ ค๊ณ ํฉ๋๋ค. ์ฐ๊ตฌ์๋ ํฌ๊ธฐ๊ฐ N x M์ธ ์ง์ฌ๊ฐํ์ผ๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, ์ง์ฌ๊ฐํ์ 1 x 1 ํฌ๊ธฐ์ ์ ์ฌ
N x N ํฌ๊ธฐ์ ์ํ๊ด์ด ์์ต๋๋ค. ์ํ๊ด์ 1 x 1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ง๋ฉฐ, ํน์ ํ ์์น์๋ ๋ฐ์ด๋ฌ์ค๊ฐ ์กด์ฌํ ์ ์์ต๋๋ค. ๋ฐ์ด๋ฌ์ค์ ์ข ๋ฅ๋ 1 ~ K๋ฒ๊น์ง K๊ฐ์ง๊ฐ ์์ผ๋ฉฐ ๋ชจ๋ ๋ฐ์ด๋ฌ์ค๋ ์ด ์ค ํ๋์ ์ํฉ๋๋ค. ์ํ๊ด์ ์กด์ฌํ๋ ๋ชจ๋ ๋ฐ์ด๋ฌ์ค๋ 1์ด๋ง๋ค ์
N๊ฐ์ ์๋ก ์ด๋ฃจ์ด์ง ์์ด A1, A2, ... AN์ด ์ฃผ์ด์ง๋๋ค. ๋, ์์ ์ ์ฌ์ด์ ๋ผ์ ๋ฃ์ ์ ์๋ N-1๊ฐ์ ์ฐ์ฐ์๊ฐ ์ฃผ์ด์ง๋๋ค. ์ฐ์ฐ์๋ ๋ง์ (+), ๋บ์ (-), ๊ณฑ์ (x), ๋๋์ (%)์ผ๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค. ์ฐ๋ฆฌ๋ ์์ ์ ์ฌ์ด์ ์ฐ์ฐ์๋ฅผ ํ๋์ฉ ๋ฃ์ด
NxN ํฌ๊ธฐ์ ๋ณต๋๊ฐ ์๋ค. ๋ณต๋๋ 1x1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ง๋ฉฐ, ํน์ ํ ์์น์๋ ์ ์๋, ํ์, ํน์ ์ฅ์ ๋ฌผ์ด ์์นํ ์ ์๋ค. ํ์ฌ ๋ช ๋ช ์ ํ์๋ค์ ์์ ์๊ฐ์ ๋ชฐ๋ ๋ณต๋๋ก ๋น ์ ธ๋์๋๋ฐ, ๋ณต๋๋ก ๋น ์ ธ๋์จ ํ์๋ค์ ์ ์๋์ ๊ฐ์์ ๋คํค์ง ์๋ ๊ฒ์ด ๋ชฉํ์ด๋ค.๊ฐ ์
์ ๋ ฌ(sorting) ์ด๋ <span style='background-color: ๋ฐ์ดํฐ๊ฐ ๋ฌด์์๋ก ์ฌ๋ฌ ๊ฐ ์์ ๋, <span style='background-color: ์ ํ ์ ๋ ฌ์ N-1๋ฒ ๋งํผ ๊ฐ์ฅ ์์ ์๋ฅผ ์ฐพ์์ ๋งจ ์์ผ๋ก ๋ณด๋ด์ผ ํ๋ค. ๋ํ ๋งค
ํ๋์ ์์ด์๋ ๋ค์ํ ์๊ฐ ์กด์ฌํ๋ค. ์ด๋ฌํ ์๋ ํฌ๊ธฐ์ ์๊ด์์ด ๋์ด๋์ด ์๋ค. ์ด ์๋ฅผ ํฐ ์ ๋ถํฐ ์์ ์์ ์์๋ก ์ ๋ ฌํด์ผ ํ๋ค. ์์ด์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ ํ๋ก๊ทธ๋จ์ ๋ง๋์์ค.์ฒซ์งธ ์ค์ ์์ด์ ์ํด ์๋ ์์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. (1<=N<=5
N๋ช ์ ํ์ ์ ๋ณด๊ฐ ์๋ค. ํ์ ์ ๋ณด๋ ํ์์ ์ด๋ฆ๊ณผ ํ์์ ์ฑ์ ์ผ๋ก ๊ตฌ๋ถ๋๋ค. ๊ฐ ํ์์ ์ด๋ฆ๊ณผ ์ฑ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋ ์ฑ์ ์ด ๋ฎ์ ์์๋๋ก ํ์์ ์ด๋ฆ์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.์ฒซ ๋ฒ์ฌ ์ค์ ํ์์ ์ N์ด ์ ๋ ฅ๋๋ค. (1<=N<=100,000)
๋๋น์ด๋ ๋ ๊ฐ์ ๋ฐฐ์ด A์ ๋ฐฐ์ด B๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ๋ ๋ฐฐ์ด์ N๊ฐ์ ์์๋ก ๊ตฌ์ฑ๋์ด ์์ผ๋ฉฐ, ๋ฐฐ์ด์ ์์๋ ๋ชจ๋ ์์ฐ์์ด๋ค. ๋๋น์ด๋ ์ต๋ K๋ฒ์ ๋ฐ๊ฟ์น๊ธฐ ์ฐ์ฐ์ ์ํํ ์ ์๋๋ฐ, ๋ฐ๊ฟ์น๊ธฐ ์ฐ์ฐ์ด๋ ๋ฐฐ์ด A์ ์๋ ์์ ํ๋์ ๋ฐฐ์ด B์ ์๋ ์์ ํ๋๋ฅผ ๊ณจ๋ผ์
๋ํ์ด๋ค ๋ฐ ํ์ N๋ช ์ ์ด๋ฆ๊ณผ ๊ตญ์ด, ์์ด, ์ํ ์ ์๊ฐ ์ฃผ์ด์ง๋๋ค. ์ด๋, ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ผ๋ก ํ์์ ์ฑ์ ์ ์ ๋ ฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์.๊ตญ์ด ์ ์๊ฐ ๊ฐ์ํ๋ ์์๋ก๊ตญ์ด ์ ์๊ฐ ๊ฐ์ผ๋ฉด ์์ด ์ ์๊ฐ ์ฆ๊ฐํ๋ ์์๋ก๊ตญ์ด ์ ์์ ์์ด ์ ์๊ฐ ๊ฐ์ผ๋ฉด ์ํ ์ ์๊ฐ ๊ฐ์ํ
์ผ์ง์ ์์ ๋ง์์ ์ฌ๋ฌ ์ฑ์ ์ง์ด ์์นํด ์์ต๋๋ค. ์ด ์ค์์ ํน๋ณํ ํ ๊ฐ์ ์ํ ๋๋ฅผ ์ค์นํ๊ธฐ๋ก ๊ฒฐ์ ํ์ต๋๋ค. ํจ์จ์ฑ์ ์ํด ์ํ ๋๋ก๋ถํฐ ๋ชจ๋ ์ง๊น์ง์ ๊ฑฐ๋ฆฌ์ ์ด ํฉ์ด ์ต์๊ฐ ๋๋๋ก ์ค์นํ๋ ค๊ณ ํฉ๋๋ค. ์ด๋ ์ํ ๋๋ ์ง์ด ์์นํ ๊ณณ์๋ง ์ค์นํ ์ ์๊ณ , ๋ ผ๋ฆฌ์ ์ผ๋ก
์ ๋ ฌ๋ ๋ ๋ฌถ์์ ์ซ์ ์นด๋๊ฐ ์์ ๋ ๊ฐ ๋ฌถ์์ ์นด๋์ ์๋ฅผ A, B๋ผ ํ๋ฉด ๋ณดํต ๋ ๋ฌถ์์ ํฉ์ณ์ ํ๋๋ก ๋ง๋๋ ๋ฐ์๋ A+B ๋ฒ์ ๋น๊ต๋ฅผ ํด์ผ ํฉ๋๋ค. ์ด๋ฅผํ ๋ฉด, 20์ฅ์ ์ซ์ ์นด๋ ๋ฌถ์๊ณผ 30์ฅ์ ์ซ์ ์นด๋ ๋ฌถ์์ ํฉ์น๋ ค๋ฉด 50๋ฒ์ ๋น๊ต๊ฐ ํ์ํฉ๋๋ค.๋งค์ฐ ๋ง์
์ด๋ฒ์๋ <span style='background-color: ๋ฐ์ดํฐ์ ๊ฐ์๊ฐ N๊ฐ์ผ ๋ ์ต๋ N๋ฒ์ ๋น๊ต ์ฐ์ฐ์ด ํ์ํ๋ฏ๋ก ์์ฐจ ํ์์ ์ต์ ์ ๊ฒฝ์ฐ ์๊ฐ ๋ณต์ก๋๋ O(N)์ด๋ค.์ด์ง ํ์(Binary Search) ์ ๋ฐฐ์ด ๋ด๋ถ์ ๋ฐ์ดํฐ๊ฐ ์ ๋ ฌ๋์ด ์์ด์ผ๋ง ์ฌ์ฉ
๋๋น์ด๋ค ์ ์ ๋งค์ฅ์๋ ๋ถํ์ด N๊ฐ ์๋ค. ๊ฐ ๋ถํ์ ์ ์ ํํ์ ๊ณ ์ ํ ๋ฒํธ๊ฐ ์๋ค. ์ด๋ ๋ ์๋์ด M๊ฐ ์ข ๋ฅ์ ๋ถํ์ ๋๋์ผ๋ก ๊ตฌ๋งคํ๊ฒ ๋ค๋ฉฐ ๋น์ผ ๋ ๊ฒฌ์ ์๋ฅผ ์์ฒญํ๋ค. ๋๋น์ด๋ ๋๋ฅผ ๋์น์ง ์๊ณ ์๋์ด ๋ฌธ์ํ ๋ถํ M๊ฐ ์ข ๋ฅ๋ฅผ ๋ชจ๋ ํ์ธํด์ ๊ฒฌ์ ์๋ฅผ ์์ฑํด์ผ ํ๋ค
์ค๋ ๋๋น์ด๋ ์ฌํ ๊ฐ์ ๋ถ๋ชจ๋์ ๋์ ํด์ ๋ก์ง ์ผ์ ํ๊ธฐ๋ก ํ๋ค. ์ค๋์ ๋ก๋ณถ์ด ๋ก์ ๋ง๋๋ ๋ ์ด๋ค. ๋๋น์ด๋ค ๋ก๋ณถ์ด ๋ก์ ์ฌ๋ฐ๊ฒ๋ ๋ก๋ณถ์ด ๋ก์ ๊ธธ์ด๊ฐ ์ผ์ ํ์ง ์๋ค. ๋์ ์ ํ ๋ด์ง ์์ ๋ค์ด๊ฐ๋ ๋ก์ ์ด ๊ธธ์ด๋ ์ ๋จ๊ธฐ๋ก ์๋ผ์ ๋ง์ถฐ์ค๋ค.์ ๋จ๊ธฐ์ ๋์ด(H)๋ฅผ ์ง์ ํ
N๊ฐ์ ์์๋ฅผ ํฌํจํ๊ณ ์๋ ์์ด์ด ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์ด ์์ต๋๋ค. ์ด๋ ์ด ์์ด์์ x๊ฐ ๋ฑ์ฅํ๋ ํ์๋ฅผ ๊ณ์ฐํ์ธ์. ์๋ฅผ ๋ค์ด ์์ด {1,1,2,2,2,2,3}์ด ์์ ๋ x = 2๋ผ๋ฉด, ํ์ฌ ์์ด์์ ๊ฐ์ด 2์ธ ์์๊ฐ 4๊ฐ์ด๋ฏ๋ก 4๋ฅผ ์ถ๋ ฅํฉ๋๋ค.๋จ, ์ด ๋ฌธ์ ๋ ์
๊ณ ์ ์ (Fixed Point)์ด๋, ์์ด์ ์์ ์ค์์ ๊ทธ ๊ฐ์ด ์ธ๋ฑ์ค์ ๋์ผํ ์์๋ฅผ ์๋ฏธํฉ๋๋ค. ์๋ฅผ ๋ค์ด ์์ด a = {-15, -4, 2, 8 ,13}์ด ์์ ๋ a2 = 2์ด๋ฏ๋ก, ๊ณ ์ ์ ์ 2๊ฐ ๋ฉ๋๋ค. ํ๋์ ์์ด์ด N๊ฐ์ ์๋ก ๋ค๋ฅธ ์์๋ฅผ ํฌํจํ๊ณ ์์ผ๋ฉฐ,
๋ํ์ด์ ์ง N๊ฐ๊ฐ ์์ง์ ์์ ์์ต๋๋ค. ๊ฐ๊ฐ์ ์ง์ ์ขํ๋ x1, x2, ..., xn์ด๊ณ ์ง ์ฌ๋ฌ ๊ฐ๊ฐ ๊ฐ์ ์ขํ๋ฅผ ๊ฐ์ง๋ ์ผ์ ์์ต๋๋ค. ๋ํ์ด๋ ์ธ์ ์ด๋์๋ ์์ดํ์ด๋ฅผ ์ฆ๊ธฐ๊ธฐ ์ํด์ ์ง์ ๊ณต์ ๊ธฐ C๊ฐ๋ฅผ ์ค์นํ๋ ค๊ณ ํฉ๋๋ค. ์ต๋ํ ๋ง์ ๊ณณ์์ ์์ดํ์ด๋ฅผ ์ฌ์ฉํ
ํ์ค ์ธ๊ณ์๋ ๋ค์ํ ๋ฌธ์ ๊ฐ ์๋ค. ๊ทธ๋ฐ๋ฐ ์ด ์ค์์ ์ปดํจํฐ๋ฅผ ํ์ฉํด๋ ํด๊ฒฐํ๊ธฐ ์ด๋ ค์ด ๋ฌธ์ ๋ ๋ฌด์์ผ๊น? ์ต์ ์ ํด๋ฅผ ๊ตฌํ๊ธฐ์ ์๊ฐ์ด ๋งค์ฐ ๋ง์ด ํ์ํ๊ฑฐ๋ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ด ๋งค์ฐ ๋ง์ด ํ์ํ ๋ฌธ์ ๋ฑ์ด ์ปดํจํฐ๋ก๋ ํด๊ฒฐํ๊ธฐ ์ด๋ ค์ด ๋ฌธ์ ์ด๋ค. ์ปดํจํฐ๋ ์ฐ์ฐ ์๋์ ํ๊ณ๊ฐ ์๊ณ
์ ์ X๊ฐ ์ฃผ์ด์ง ๋ ์ ์ X์ ์ฌ์ฉํ ์ ์๋ ์ฐ์ฐ์ ๋ค์๊ณผ ๊ฐ์ด 4๊ฐ์ง์ด๋ค.X๊ฐ 5๋ก ๋๋์ด ๋จ์ด์ง๋ฉด, 5๋ก ๋๋๋ค.X๊ฐ 3์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ฉด, 3์ผ๋ก ๋๋๋ค.X๊ฐ 2๋ก ๋๋์ด ๋จ์ด์ง๋ฉด, 2๋ก ๋๋๋ค.X์์ 1์ ๋บ๋ค.์ ์ X๊ฐ ์ฃผ์ด์ก์ ๋, ์ฐ์ฐ 4๊ฐ๋ฅผ ์ ์ ํ
๊ฐ๋ฏธ ์ ์ฌ๋ ๋ถ์กฑํ ์๋์ ์ถฉ๋นํ๊ณ ์ ๋ฉ๋๊ธฐ ๋ง์์ ์๋์ฐฝ๊ณ ๋ฅผ ๋ชฐ๋ ๊ณต๊ฒฉํ๋ ค๊ณ ํ๋ค. ๋ฉ๋๊ธฐ ๋ง์์๋ ์ฌ๋ฌ ๊ฐ์ ์๋์ฐฝ๊ณ ๊ฐ ์๋๋ฐ ์๋์ฐฝ๊ณ ๋ ์ผ์ง์ ์ผ๋ก ์ด์ด์ ธ ์๋ค. ๊ฐ ์๋์ฐฝ๊ณ ์๋ ์ ํด์ง ์์ ์๋์ ์ ์ฅํ๊ณ ์์ผ๋ฉฐ ๊ฐ๋ฏธ ์ ์ฌ๋ ์๋์ฐฝ๊ณ ๋ฅผ ์ ํ์ ์ผ๋ก ์ฝํํ์ฌ ์๋์