์ด ๊ธ์ ํฌ๋ฆฌ์ค๋ง์ค์ ์ด๋ฆฐ (!!) AHC 29์ 3์๊ฐ ์ ๋ ํ์ด๋ณด๊ณ ๋์ถฉ ์ด ํ๊ธฐ๊ธ์ด๋ค.
5์ข
๋ฅ์ ํน์ํ ๊ธฐ๋ฅ์ ํ๋ ์นด๋๊ฐ ์๋ค. ๊ทธ๋ฆฌ๊ณ ํ๋ก์ ํธ๋ ์๋ค. ์ด ์นด๋๋ฅผ ์ฌ์ฉํด์ ํ๋ก์ ํธ๋ฅผ ์งํ์ํฌ ์ ์๋๋ฐ, ํ๋ก์ ํธ์ ์์ ํ์ฌ ๋ค๊ณ ์๋ ์นด๋ ์๋ TC
๋ง๋ค ๋ค๋ฅด๋ค.
๋๋ ๊ฐ๋จํ๊ฒ ๊ธฐ๋ณธ ์นด๋ (๋์ด ์๋ค๊ณ , ์ผ์ ๋์ ์ผ์ ํ๋ ์นด๋๊ฐ ํญ์ ์ฃผ์ด์ง๋ค) ๋ฅผ ๊ณ์ ์ฌ์ฉํ๋ค๊ฐ, ์ด๋ ์๊ฐ ์ ์ฒด ์ผ์ ํ๋ ์นด๋๊ฐ ํจ์จ์ด ์ข์ ์๊ฐ์ด ์ค๋ฉด ์ฌ์ฉํ๋ ๊ฐ๋จํ ์ ๋ต์ ์ฌ์ฉํ๋ค.
๋ ํฌ์ ์นด๋๊ฐ ์๋๋ฐ, ํฌ์ ์นด๋๋ ์ ์ฒด ํด์ 75%๊ฐ ์ง๋๊ธฐ ์ ์ด๋ฉด ๋ฌด์กฐ๊ฑด ๊ตฌ๋งคํ๊ฒ ํ๋ค.
์ด๋ฐ ๋ฅ์ ๋ฌธ์ ๊ฐ ๋์ค๋ฉด ์ด๋ป๊ฒ ์ ๊ทผํ ์ง ์ ๋ชจ๋ฅด๊ฒ ๋ค. ์นด๋์ ์ฌ์ฉ์ ๊ทธ๋ํ๋ก ๋ํ๋ผ ์ ์๋? ์๋ฌดํผ ์ ๊ทผ ๋ฐฉ๋ฒ ์์ฒด๊ฐ ์ ์๋ณด์ฌ์, ๊ทธ๋ฅ ์ด์ ๋์ Greedy
์๋ฃจ์
์ ์ ์ถํ๊ณ ๋๋๋ค.