[BOJ][Python]11053번 풀이

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

11053번: 가장 긴 증가하는 부분 수열

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

이번 문제는 그렇게 어렵지 않은데 좀 헤맸네요. 점화식을 세우는데에 고생을 좀 했습니다.

 

문제 접근은 dp로 하시면 됩니다. 좀 쉽게 푸는 방법이 있나 싶어서 검색을 해봤는데 재귀로 푸신 분들도 꽤 있더라구요. 저는 재귀로 푸는 방법은 생각이 잘 나지 않아서 이번 포스팅에서는 dp로 푸는 방법을 설명해드리겠습니다. 일단 n의 범위가 1000까지로 상당히 작습니다. 시간제한은 1초 정도 되니 O(n^2)정도면 넉넉하게 돌아가겠네요. 그렇다면 어차피 크고 작음을 비교해서 증가하는 수열인지를 판단하므로 대놓고 이중 반복문으로 풀라고 힌트를 주는 것과 다름없는 것 같습니다. 따라서 이중 반복문을 이용한 풀이로 진행을 합니다. 주어진 입력에서 dp는 1로 초기화를 하는데 그 이유는 해당 리스트가 가지는 의미가 수열의 길이라서 그렇습니다(정확하게는 인덱스에 따른 최적의 길이). 리스트를 초기화 시켜놓은 다음부터는 반복문에서 각각 비교하면서 조건에 맞는 값을 리스트에 넣어주면 되겠네요(원래 길이가 더 긴지 i에 대해 1 추가된 길이가 더 긴지 비교).