BAEKJOON : 11053

No. 11053

1. Problem

2. My Solution

• dp 리스트에 요소로 끝나는 부분 수열의 길이를 저장하고 이를 이용하여 가장 큰 길이 값을 구함 -> DP

• 첫 번째 방법
• 2 1 2 입력 시 1로 출력되는 버그 발생 (자신 보다 작은 요소가 없으면 0으로 처리됨)

import sys

n = int(sys.stdin.readline().rstrip())   # n = 6 
seqeunce = [0] +list(map(int,sys.stdin.readline().rstrip().split()))   
dp = [0] * (n+1)
 
for i in range(1,n+1): # 1~6
    if i == 1:
        dp[1] = 1
    else:
        for j in range(1,i): # 최대 1~5
            if seqeunce[j] < seqeunce[i]:
                dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

• 두 번째 방법

import sys

n = int(sys.stdin.readline().rstrip())   # n = 6 
seqeunce = [0] +list(map(int,sys.stdin.readline().rstrip().split()))   
dp = [1] * (n+1)
 
for i in range(1,n+1): # 1~6
    for j in range(1,i): # 최대 1~5
        if seqeunce[j] < seqeunce[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

3. Learned

• 특정 저장공간(메모리)에 이전의 결과 값을 저장하고 있고, 다음 값을 계산할 때 이전 값들을 이용한다면 dp라고 볼 수 있음