다이나믹 프로그래밍 연습을 위해서 다이나믹 프로그래밍 문제를 더 풀어보았다. 이번에는 이전 수들 중에서 자신보다 작은 수에 대한 dp값을 비교하여 더 큰 값으로 갱신하는 방식으로 해결하였다. 1, 5, 2, 3, 7로 예를 들어보면 다음과 같다.

• dp배열을 1로 초기화한다.
• 1 이전에 작은 상자가 없으므로 dp[0]은 1로 유지한다.
• 5 이전에 1이 있으므로 dp[1]은 2로 갱신한다.
• 2 이전에 1이 있으므로 dp[2]는 2로 갱신한다.
• 3 이전에 1이 있으므로 dp[3]은 2로 갱신한다.
  -> 2가 있으므로 dp[3]은 3으로 갱신한다.
• 7 이전에 1이 있으므로 dp[4]는 1로 갱신한다.
  -> 5가 있으므로 dp[4]는 3으로 갱신한다.
  -> 2가 있으므로 dp[4]는 3으로 유지한다.
  -> 3이 있으므로 dp[4]는 4로 갱신한다.
• dp중 가장 큰 수인 4가 도출된다.

코드는 다음과 같이 작성하였다.

• n을 입력받는다.
• 상자의 크기를 나타내는 배열 box를 입력받는다.
• dp배열을 1 n개로 초기화한다.
• n만큼 반복하는 i에 대한 for문을 돌린다.
  -> i만큼 반복하는 j에 대한 for문을 돌린다.
  --> box[j]보다 box[i]가 더 클 경우 dp[i]를 dp[i]와 dp[j]+1 중 더 큰 값으로 갱신한다.
• dp중 가장 큰 값을 출력한다.

Code

n=int(input())
box=list(map(int, input().split()))
dp=[1]*n
for i in range(n):
    for j in range(i):
        if box[j]<box[i]:
            dp[i]=max(dp[i], dp[j]+1)
print(max(dp))