songining
article thumbnail
[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 ..