
[DP] ๋ฐฑ์ค 14501 ๋ฌธ์ ํ์ด
ALGORITHM
2020. 9. 16. 23:20
์ด ๋ฌธ์ ๋ ์๊ฐํ ๊ฒ ๋ณด๋ค ์ด๋ ค์ ๋ค. DP๋ก ํ์ด์ผ๊ฒ ๋ค๊ณ ์๊ฐ์ ํ๊ณ ์งฐ๋๋ฐ ๋ฐฐ์ด 1์์๋ถํฐ ์์ํ๋ ๋ ์ง ๊ณ์ฐ์ ์ด๋ป๊ฒ ํด์ผํ ์ง ๊ฐ์ด ์์๋ค. ๊ทธ๋์ ์๋ด์ก๋ ์์๋ฅผ ๋ง์ง๋ง๋ ์์๋ถํฐ ์์ํ์๋ค. ์ผ๋จ ์๋ด์ ์ก์์ ์๋ ๋ ๊ณผ ์๋ด์ ์ก์ ์ ์๋ ๋ ๋ก ์กฐ๊ฑด์ ๋๋๋ค. 1. ์๋ด์ ์ก์ผ๋ฉด ํด์ฌ์ผ์ ๋๊ธฐ๋ ๊ฒฝ์ฐ DP[i] = DP[i+1] ์ ๋ ์ ์ก์ ์๋ด ๊ฐ๊ฒฉ ๋์ 2. ์๋ด ์ก์ ์ ์๋ ๊ฒฝ์ฐ max(DP[i+1], DP[i+time[i]]+Price[i]) ์ ๋ ์ ์ก์ ์๋ด๊ฐ๊ฒฉ๊ณผ (์ค๋์๋ด๊ฐ๊ฒฉ+์๋ด์ผ์ง๋ํ์ ์๋ด๊ฐ๊ฒฉ) ์ค ํฐ ๊ฐ def main(): n = int(input()) max_price_list = [0 for _ in range(n + 2)] time_list = [0 for _ in ..