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

문제

#11053 가장 긴 증가하는 부분 수열
Silver2
적용 알고리즘: 동적 계획법 알고리즘

---

풀이 방법

• 첫 번째 값을 알고 있다. 첫 번째 수까지의 가장 긴 증가하는 부분 수열은 1이다.
• 별도의 배열(cnt)을 지정하여, 각 숫자(단계)까지의 가장 긴 증가하는 부분 수열 길이의 최댓값을 저장한다.
• 이전 수 중에서 현재 수보다 작은 수 중에서 가장 큰 길이를 가진 수 + 1이 현재의 수가 된다.

코드 흐름

1. 사용자에게서 입력을 받는다.
2. 입력된 각 숫자까지의 가장 긴 증가하는 부분 수열을 저장하는 배열(cnt)을 생성한다. 해당 배열의 첫 번쨰 값은 1이다.
3. 두 번째 숫자부터 n번째 숫자까지 루프를 돌린다.
4. 0번쨰 원소부터 현재 수 이전까지 루프를 돌린다. 만약 내부 루프 의 값(j)이 현재 수보다 작으면, j번째 원소의 (계산해 놓았던) j번째까지의 가장 긴 증가하는 부분 수열의 값(cnt)을 임시 배열(temp)에 넣는다.
5. 임시 배열(temp)에서의 가장 큰 값을 구하고, 그 값에 1을 더한 값이 현재 수까지의 가장 긴 증가하는 부분 수열의 길이가 된다.
6. 각 숫자까지의 가장 긴 증가하는 부분 수열을 저장하는 배열(cnt)에서 가장 큰 값을 구한다.

코드

n = int(input())
a = [int(m) for m in input().split()]

cnt = [0] * n
cnt[0] = 1      # 첫째 수까지는 1개임

for i in range(1, n):
    temp = [0] * n

    for j in range(0, i):
        if (a[j] < a[i]):
            temp[j] = cnt[j]
    cnt[i] = max(temp) + 1

print(max(cnt))

체감 난이도: 4/5
동적 계획법 문제를 몇개 풀어서 처음 접근이 조금 쉬웠던 것 같다. 시간제한이 1초라 이중 루프를 돌리는게 맞나 생각했었는데 이중 루프 정도는 1초만에 가능한 것 같다..ㅎㅎ 이젠 시간초과가 되는 것에 대한 걱정이 점점 생기는 것 같다. 동적 계획법으로 접근하기 위해서는 처음 초기값을 먼저 파악하고, 이를 상향식으로 할지 하향식으로 할지 선택하는 것도 중요한 것 같고, 문제를 푸는 과정에서는 이를 저장할 배열이 필요한 것 같다.
다른 풀이를 찾아보니 max 함수로 두개의 값 중에 하나를 선택하는 풀이도 있던데 오히려 두개중 택을 하는 방법으로 코드를 짜는 것이 더 어려운 것 같다… 나는 그냥 무식? 하게 모든 값을 다 때려넣고 그 중에서 max를 택하는 방법을 택했다…