[Python Algorithm] 가장 긴 증가하는 수열 BOJ #11053

문제

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

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

 

내 문제 풀이

n = int(input())
permu = list(map(int, input().split()))
count = [1] # 첫 번째 숫자의 길이는 어차피 1이므로 미리 추가
counting = 0

def find(now):
    global counting
    for i in reversed(range(len(count))):
        if counting < count[i] and permu[i] < now:
            counting = count[i]

for i in range(1, n):
    find(permu[i])
    count.append(counting+1)
    counting = 0

print(max(count))

👉 DP 문제로, 나보다 작은 가장 긴 증가하는 수열에 대한 카운트를 누적하는 것이 포인트 !

• 주어진 permu 리스트를 순차적으로 돌면서 find 함수를 실행해주었다.
  find 함수는 현재 숫자를 인자로 받는데, 현재 숫자 이전의 숫자들을 검사하면서,
  현재 숫자보다 작은 수 중에 count에 저장된 값이 가장 큰 값을 counting에 저장했다.
• 그리고 find에서 구한 counting에 1을 더한 값을 count 리스트에 추가했고,
  다음 반복이 시행되기 전 counting 변수는 다시 0으로 초기화했다.
• 이러한 시행을 반복하여 count에 저장된 값 중 가장 큰 값을 출력했다.

➕ 이 문제는 아주 전형적인 LIS 문제이므로, 같이 보면 좋을 것 같아 추가한다.

https://seolhee2750.tistory.com/109?category=872093 

[Swift Algorithm Note] 최장 증가 부분 수열 (feat. DP)

 

💡 피드백

• 쉬운 문제지만, LIS 유형을 모른다면 생각하기 어려울 수 있는 문제같다.
  나도 DP 자체를 오랜만에 풀었더니 시간이 좀 걸렸다.