[백준-11053] 가장 긴 증가하는 부분 수열

문제

링크

코드

n = int(input())

numList = list(map(int, input().split()))

answer = [1] * n

for i in range(len(numList)) :
    for j in range(0, i) :
        if numList[i] > numList[j] :
            answer[i] = max(answer[j] + 1, answer[i])
            
print(max(answer))

풀이

numList에 수열을 넣고 반복문을 돌리면서 인덱스가 작을 때 값도 작은 수가 몇 개인지 확인하는 방법으로 진행했다. 다른 분들의 코드, 풀이를 참고하면서 풀었다.

다음과 같이 점화식을 구할 수 있다.

answer[i] = max(answer[j] + 1, answer[i])

배열의 현재 수보다 이전 수들이 작을 때마다 현재 수의 answer 값이 1씩 더해진다.
이때 이전 수의 answer +1 과 현재 수의 answer를 비교해서 큰 값이 저장된다.
현재 수의 answer와 비교하는 이유는 현재 비교하기 전에도 또 비교를 하고 넘어왔을 수도 있기 때문이다. (i를 기준으로 i보다 작은 값인 j를 통해 비교)