SWEA 3307 최장 증가 부분 수열(with Python)

내가 생각한 Solution

문제에서 생각해볼 점

• 처음에 재귀를 활용했는데, 시간초과가 발생했습니다.

• 따라서 DP로 접근해서 풀었습니다. (아래 그림 참조)

• 한번에 이해하기 힘들 것으로 예상됩니다. 예제를 천천히 직접 손으로 그려가며 방법을 이해하시면 좋을 것 같습니다.

코드 구현

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    numbers = list(map(int, input().split()))
    dp = [0] * N
    dp[0] = 1

    for i in range(1, N):
        maxV = 0
        # 현재 위치 원소 인덱스보다 작은 인덱스 값을 가지는 원소 탐색
        for j in range(i-1, -1, -1):
            # 탐색하다가 나보다 작은 숫자라면
            if numbers[i] >= numbers[j]:
                # 이때까지의 최장 길이 값을 저장
                if maxV < dp[j]:
                    maxV = dp[j]
        dp[i] = maxV + 1

    print(f'#{tc} {max(dp)}')