๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

DP

Algorithm/๋ฐฑ์ค€ [๋ฐฑ์ค€] #14501 ํ‡ด์‚ฌ (Python) ํ‡ด์‚ฌ ๋ฌธ์ œ ํ‡ด์‚ฌ๋ฅผ ์ง„ํ–‰ํ–‰ํ•˜๋ ค ํ•˜๋Š”๋Š”๋ฐ N+1์ผ ์งธ ๋˜๋Š”๋‚  ํ‡ด์‚ฌ๋ฅผ ํ•˜๊ธฐ ์œ„ํ•ด์„œ N์ผ ๋™์•ˆ ๋งŽ์€ ์ƒ๋‹ด์„ ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ์ƒ๋‹ด์„ ์™„๋ฃŒํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„ T์™€ ์ƒ๋‹ด์„ ํ–ˆ์„ ๋•Œ ๋ฐ›์„ ์ˆ˜ ์žˆ๋Š” ๊ธˆ์•ก P๋ฅผ ๋ณด๊ณ , ํ‡ด์‚ฌ ์ „๊นŒ์ง€ ์ตœ๋Œ€ ์ˆ˜์ต์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ์˜ˆ์ œ 1์ผ 2์ผ 3์ผ 4์ผ 5์ผ 6์ผ 7์ผ Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 ์ž…๋ ฅ 7 3 10 5 20 1 10 1 20 2 15 4 40 2 200 ์ถœ๋ ฅ 45 ๋ฌธ์ œ ํ’€์ด ์ „๋žต day 0 1 2 3 4 5 6 Ti 3 5 1 1 2 3 2 Pi 10 20 10 20 15 40 200 day๋Š” 0~n-1, ํ‡ด์‚ฌ์ผ n dp ๋ฐฉ์‹์œผ๋กœ ํ‘ผ๋‹ค dp[day] = max(dp[day+1],dp[day+T[day]]+P[day]) day์—์„œ..

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”