백준 11053 가징긴증가부분수열

가징긴증가부분수열(백준 11053)

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

단순히 반복문을 2번 돌면 풀 수 있다고 생각하였으나,
접근 방식이 미묘하게 틀려,
(비교값 중 가장 큰 값을 저장하는 방식을 사용했으나 반례를 통해
확인하였다)
삽질 후,
내가 처음 짠 방식으로는 접근할 수 없다고 판단하여,
아이디어를 확인한 후, 해결하였다

Code

import sys

inp = sys.stdin.readline

num = int(inp().strip())

nList = list(map(int,inp().split()))

# lcs 변형
# 같은 문자열 2번 비교

# 아무리 수열이 작아도 최소 1의 길이가 보장됨
dp = [1 for _ in range(num)]

# dp[i] = nList[i]를 마지막 값으로 가지는 가장 긴 증가부분 수열의 길이

for i in range(num):
    # 1 ... i 까지 반복문을 돌려
    # dp를 채운다
    for j in range(i): # 이게 num이여도 정답이지만... 기본적으론 정의에 어긋나고 가독성이 떨어진다
        if nList[i] > nList[j]: # 현재 문자열이 다른 문자열보다 크다면
            dp[i] = max(dp[i],dp[j]+1) # 가장 긴 증가 부분 수열의 길이를 가진 녀석보다 1 크게 만들어준다

# dp 중 가장 긴 수를 반환한다
print(max(dp))

해결 아이디어

1. dp 초기화(아무리 수열이 작아도 1의 길이는 나오므로)
   
2. 내부를 2번 돌아야 하므로 2중 for 문 사용
   
3. i는 점차 증가하며, j는 0부터 i까지 돌며 dp를 채우는 용도
   
4. i번째의 입력값이 j 번쨰 입력값보다 크다면,
   해당 dp[j]를 확인하고, 현재 값보다 큰지 확인하기
   
5. dp 중 가장 큰 값을 반환