๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜

[๋ฐฑ์ค€] 11055 - ๊ฐ€์žฅ ํฐ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด (DP)

by young-ji 2022. 10. 12.

https://www.acmicpc.net/problem/11055

 

11055๋ฒˆ: ๊ฐ€์žฅ ํฐ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด

์ˆ˜์—ด A๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ทธ ์ˆ˜์—ด์˜ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด ์ค‘์—์„œ ํ•ฉ์ด ๊ฐ€์žฅ ํฐ ๊ฒƒ์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ˆ˜์—ด A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} ์ธ ๊ฒฝ์šฐ์— ํ•ฉ์ด ๊ฐ€์žฅ ํฐ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜

www.acmicpc.net

 

๋‚œ์ด๋„ : ํ•˜

DP ๊ธฐ๋ณธ ๋ฌธ์ œ

 

import sys

n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))


dp = [0]*n 
for i in range(n) :
  dp[i] = a[i] # ์ž๊ธฐ์ž์‹ ๋งŒ ์ˆ˜์—ด์ธ ๊ฒฝ์šฐ

for i in range(n):
  for j in range(i):
    if a[i] > a[j]:
      dp[i] = max(dp[j]+ a[i],dp[i])

print(max(dp))

๋Œ“๊ธ€