baekjoon - 11053

problem. 주어진 수열 중에서 가장 긴 부분의 length를 찾는 문제

 

key point.

이 문제를 최장 증가 부분 수열이라고 부른다. 그래서 이 알고리즘을 사용해서 문제를 풀면 바로 해결이 된다. 자세한 것은 algorithm study 카테고리에 작성할 것이다.

 

import sys n = int(input()) ls = list(map(int, sys.stdin.readline().split())) dp = [1] * n // 기본적인 길이는 1이기 때문에 default value를 1로 해준다. for i in range(n):     for j in range(i):         if ls[j] < ls[i]:             dp[i] = max(dp[i], dp[j] + 1)              print(max(dp))

 

처음에 이해하는 게 조금 어려웠는데 인강도 듣고 직접 케이스를 찾아서 작성해보니까 이해가 됐다.

이런 알고리즘을 어떻게 작성하는 건지.. 다들 대단하다