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

😲 문제

출처
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력
6
10 20 10 30 20 50

출력
4

❗️ 문제 재정의

등차 수열, 등비 수열이 아니다.
그저 가장 긴 증가하는 수열을 찾으면 된다.
가장 긴 증가하는 수열이란 것에 대한 조건을 생각해보자

1. 앞의 인덱스에 해당하는 뒤에 있는 인덱스에 해당하는 숫자보다 커야한다.
2. 나의 뒤에 있는 인덱스까지의 길이 중 가장 최대값에 +1하면 된다.

✔ 계획 수립

1. 입력받기
2. dp 배열 1로 초기화 (길이가 1일때는 자기 자신)
3. 인덱스 탐색 1~n까지 (i)
4. i 인덱스보다 뒤에 있는 값들 중 자신보다 작은 것들을 선택 (j)
5. 자신보다 작은 것들 중 가장 최대 길이를 선택 (max)

핵심은 기존 수열의 순서를 바꿀 수는 없다.
길이 i를 선정했다면 i의 뒤에 있는 것들 중 가장 큰 값에 자기자신의 길이(1)을 더한 것이 가장 긴 수열이라는 의미이다.

👨🏻‍💻 문제 풀이

n = int(input()) # 입력 숫자의 수
sequence = list(map(int, input().split())) # 입력 수열
d = [1] * n # d 초기화
# i의 뒤에 있는 인덱스들에서 가장 최대값을 찾는데 그 수가 나보다 작아야함.
for i in range(1,n): # 길이가 2인 것들부터 탐색 
    max_value = 0
    for j in range(i): # 선정된 인덱스에서 뒤에까지 최대 길이
        if sequence[i] > sequence[j]:
            max_value = max(max_value, d[j])
    d[i] += max_value
print(max(d))

[10 20 10 30 20 50]

[1, 2, 1, 1, 1, 1] # i = 1 -> 1+1(자기자신)
[1, 2, 1, 1, 1, 1] # i = 2 -> 10보다 작은 것은 없음
[1, 2, 1, 3, 1, 1] # i = 3 -> 2+1(자기자신)
[1, 2, 1, 3, 2, 1] # i = 4 -> 1+1(자기자신)
[1, 2, 1, 3, 2, 4] # i = 5 -> 3+1(자기자신)
4

😅 회고

솔직히 이 문제를 30분 넘게 붙잡고 있었다는 것에 자존심이 상한다.
빠르게 판단하고 사고하는 것이 필요할 듯 싶다.
수열의 조건이 무엇인가 가장 길게 하려면 어떻게 해야하는가
그 다음 문제를 작게 쪼갤 수 있는가?
큰 문제 안에 작은 문제가 포함 되는가?

간단한 문제를 풀더라도 좀 순차적으로 접근하자...