Python3,DP
문제
입출력
입출력 예시
주요 포인트
11053과 마찬가지로 이중 반복문이 사용된다.
i는 1부터 n-1까지 순회하고, j는 0부터 i-1까지 순회한다.
이때 수열[i]와 수열[j]를 비교하고 수열[i]가 더 크면 dp[i]와 dp[j] + a[i] 중 더 큰 값을 넣는다.
if문을 통과한 dp는 다음과 같다.
[1, 101, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 101, 3, 0, 0, 0, 0, 0, 0, 0]
[1, 101, 3, 51, 0, 0, 0, 0, 0, 0]
[1, 101, 3, 53, 0, 0, 0, 0, 0, 0]
(중략)
[1, 101, 3, 53, 113, 6, 11, 17, 24, 32]
[1, 101, 3, 53, 113, 6, 11, 17, 24, 32]
최종 코드
n = int(input())
dp = [0 for i in range(n)]
a = list(map(int, input().split()))
dp[0] = a[0]
for i in range(1, n):
for j in range(i):
if a[i] > a[j]:
dp[i] = max(dp[i], dp[j] + a[i])
else:
dp[i] = max(dp[i], a[i])
print(dp)피드백
a[i]가 a[j] 보다 클 때, dp[i]와 dp[j] + a[i] 두 수 중 비교해서 더 큰 수를 넣어야 한다는 것에 접근하는 게 어려웠다.
또 그렇지 않을 때는 dp[i]와 a[i]를 비교해서 더 큰 수를 넣어야 한다.
I mean