โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/2579 2579๋ฒ: ๊ณ๋จ ์ค๋ฅด๊ธฐ ๊ณ๋จ ์ค๋ฅด๊ธฐ ๊ฒ์์ ๊ณ๋จ ์๋ ์์์ ๋ถํฐ ๊ณ๋จ ๊ผญ๋๊ธฐ์ ์์นํ ๋์ฐฉ์ ๊น์ง ๊ฐ๋ ๊ฒ์์ด๋ค. ๊ณผ ๊ฐ์ด ๊ฐ๊ฐ์ ๊ณ๋จ์๋ ์ผ์ ํ ์ ์๊ฐ ์ฐ์ฌ ์๋๋ฐ ๊ณ๋จ์ ๋ฐ์ผ๋ฉด ๊ทธ ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ www.acmicpc.net ์
๋ ฅ ์
๋ ฅ์ ์ฒซ์งธ ์ค์ ๊ณ๋จ์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ ํ ์ค์ ํ๋์ฉ ์ ์ผ ์๋์ ๋์ธ ๊ณ๋จ๋ถํฐ ์์๋๋ก ๊ฐ ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ๊ณ๋จ์ ๊ฐ์๋ 300์ดํ์ ์์ฐ์์ด๊ณ , ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๋ 10,000์ดํ์ ์์ฐ์์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๊ณ๋จ ์ค๋ฅด๊ธฐ ๊ฒ์์์ ์ป์ ์ ์๋ ์ด ์ ์์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ dp ๋ฌธ์ ์ด๋ฏ๋ก ์ ํ์์ ์ฐพ์์ผํ๋ค. ๋์ฐฉ์ง์ ์ ๊ฐ ์ ์๋ ๋ฐฉ๋ฒ์ ์ด๋ป๊ฒ ๋ ๊น? ๋ ..
โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/1932 1932๋ฒ: ์ ์ ์ผ๊ฐํ ์ฒซ์งธ ์ค์ ์ผ๊ฐํ์ ํฌ๊ธฐ n(1 โค n โค 500)์ด ์ฃผ์ด์ง๊ณ , ๋์งธ ์ค๋ถํฐ n+1๋ฒ์งธ ์ค๊น์ง ์ ์ ์ผ๊ฐํ์ด ์ฃผ์ด์ง๋ค. www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ ์ผ๊ฐํ์ ํฌ๊ธฐ n(1 โค n โค 500)์ด ์ฃผ์ด์ง๊ณ , ๋์งธ ์ค๋ถํฐ n+1๋ฒ์งธ ์ค๊น์ง ์ ์ ์ผ๊ฐํ์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฒฝ๋ก์ ์๋ ์์ ํฉ์ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ ์ด์ ๋ฌธ์ ์๋ RGB ๊ฑฐ๋ฆฌ ๋ฌธ์ ์ ์ ์ฌํ๋ค. dp๋ฅผ ์ด์ฉํ ๊ฒ์ด๋ฏ๋ก ์ ํ์, ์ฆ ๊ท์น์ ์ฐพ์๋ด์ผ ํ๋ค. ์ฒซ๋ฒ์งธ ํ์ ๋ฌด์กฐ๊ฑด ์๊ธฐ ์์ ์ ํํ๋ฏ๋ก ์ ์ธ ๋๋ฒ์งธ ํ๋ถํฐ๋ i) ๊ฐ์ฅ ์ข์ธก ์์์ ๊ฒฝ์ฐ ์ด์ ํ์ ๊ฐ์ฅ ์ข์ธก ์์ ii) ๊ฐ์ฅ ์ฐ์ธก ์์์ ๊ฒฝ์ฐ ์ด์ ํ์ ๊ฐ์ฅ ์ฐ์ธก ์์๋ฅผ ๋ฌด..
โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/1149 1149๋ฒ: RGB๊ฑฐ๋ฆฌ ์ฒซ์งธ ์ค์ ์ง์ ์ N(2 โค N โค 1,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๊ฐ ์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋์ผ๋ก ์น ํ๋ ๋น์ฉ์ด 1๋ฒ ์ง๋ถํฐ ํ ์ค์ ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ง์ ์น ํ๋ ๋น์ฉ์ 1,000๋ณด๋ค ์๊ฑฐ๋ www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ ์ง์ ์ N(2 โค N โค 1,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๊ฐ ์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋์ผ๋ก ์น ํ๋ ๋น์ฉ์ด 1๋ฒ ์ง๋ถํฐ ํ ์ค์ ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ง์ ์น ํ๋ ๋น์ฉ์ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๋ชจ๋ ์ง์ ์น ํ๋ ๋น์ฉ์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ ์ด ๋ฌธ์ ์ ์๊ฐ ์ ํ์ 0.5์ด๋ก ์งง๋ค. ์ค์ฒฉ ๋ฐ๋ณต๋ฌธ์ ์ด์ฉํ ๋ธ๋ฃจํธ ํฌ์ค์ ๋ฐฉ๋ฒ..
โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/9461 9461๋ฒ: ํ๋๋ฐ ์์ด ์ค๋ฅธ์ชฝ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์ผ๊ฐํ์ด ๋์ ๋ชจ์์ผ๋ก ๋์ฌ์ ธ ์๋ค. ์ฒซ ์ผ๊ฐํ์ ์ ์ผ๊ฐํ์ผ๋ก ๋ณ์ ๊ธธ์ด๋ 1์ด๋ค. ๊ทธ ๋ค์์๋ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์ ์ผ๊ฐํ์ ๊ณ์ ์ถ๊ฐํ๋ค. ๋์ ์์ ๊ฐ์ฅ ๊ธด ๋ณ์ www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , N์ด ์ฃผ์ด์ง๋ค. (1 โค N โค 100) ์ถ๋ ฅ ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ง๋ค P(N)์ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ ์ฒ์ ๋ค์ด๋ณด๋ ์๋ก์ด ์์ด์ด์ง๋ง ๊ทธ ๊ท์น์ ํผ๋ณด๋์น์ ๋น์ทํ๋ค. ํผ๋ณด๋์น์ ์ ํ์์ด f(n) = f(n-1) + f(n-2) ์๋ค๋ฉด N 1 2 3 4 5 6 7 8 9 P(N) 1 1 1 2 2 3 4 5 7 ํ๋๋ฐ์ ์ ..