[SWEA] D3. 최장 증가 부분 수열

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWBOKg-a6l0DFAWr&categoryId=AWBOKg-a6l0DFAWr&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=4# 

SW Expert Academy

 

 

1. 해결방법

처음에는 재귀 완전탐색으로 출력은 올바르게 나왔지만 시간초과로 실패하였다.

DP 다이나믹 프로그래밍을 이용하면 시간복잡도를 해결할 수 있다.
DP를 이용해야한다는 아이디어가 떠오지 않아서 꽤나 시간을 잡아먹은 문제이다.

https://velog.io/@meganatc7/SWEA-3307.-%EC%B5%9C%EC%9E%A5-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-with-Python
위 링크에서 해설을 들으면 쉽게 이해가 갈 것이다.

 

 

2. 재귀 완전탐색 코드 (틀린 코드)

def dfs(idx, result):
    global answer

    if idx == N:
        answer = max(answer, len(result))
        return

    for j in range(idx, N):
        if chk[j] == False:
            if result[-1] < numbers[j]:
                chk[j] = True
                result.append(numbers[j])
                idx += 1
                dfs(idx, result)
                result.pop()
                chk[j] = False
            else:
                dfs(idx + 1, result)

T = int(input())
# T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    numbers = list(map(int, input().split()))
    chk = [False] * N

    answer = 0
    for i in range(N):
        if chk[i] == False:
            chk[i] = True
            dfs(i, [numbers[i]])
            chk[i] = False

    print(f"#{test_case} {answer}")

 

 

3. 정답코드 (DP)

T = int(input())
# T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    numbers = list(map(int, input().split()))

    result = [1] * N
    result[0] = 1

    for i in range(1, N):
        for j in range(i):
            if numbers[i] > numbers[j]:
                result[i] = max(result[i], result[j] + 1)

    print(f"#{test_case} {max(result)}")