접근 방법
음.. 풀지 못하였다.
DP를 사용하여 푸는 문제였는데, DP와 연이 없는 관계로 검색하여 다른 사람들의 풀이를 참고해서 풀었다...
일단, 최장 증가 부분 수열이란 무엇인가 봤더니
주어진 수열 중 증가하는 부분 수열을 말한다.
이런 식으로 수열이 존재한다면
[2,7], [2,4], [2,7,9], [1,9]가 해당 수열 내에 존재하는 증가하는 부분수열이 되는 것이다.
여기서 최장은 가장 긴 것으로 2,7,9가 된다.
그럼 이걸 어떻게 DP로 접근하느냐..
그것은 각 숫자를 마지막번째라고 가정을 하고
가정한 숫자의 앞의 숫자들이 해당 숫자보다 작고 증가하는 패턴을 찾는 것이다.
그림으로 보면,
2를 먼저 가장 마지막 숫자라고 가정한다면 길이는 1이 될 것이다.
그리고 이러한 길이를 메모해나가면서 하나의 리스트에 저장한다.
다음 7을 마지막 숫자라고 가정한다면 길이는 2가 된다.
이때, 2라는 길이는 단순히 눈으로도 알 수 있지만 앞에 메모해뒀던 1을 사용할 수 있다. 이건 뒤에 가서 9의 경우에서 알아보자
다음 4를 마지막 숫자라고 가정한다면 길이는 1이되고 이렇게 반복을 한다.
그리고 마지막 대망의 9를 살펴보자면 결론부터 말해서 7에 메모해두었던 2에 + 1을 하면 된다.
이유는, 결국 7이란 숫자 앞에는 9와 7보다 작으면서 증가하는 수열의 가장 긴 길이가 들어가 있기 때문이다. 이게 DP의 핵심이다.
다른 예로
이런 경우에는 9는 4에 메모해 두었던 값에 + 1, 혹은 3에 메모해 두었던 값에 +1이 되는 셈이다.
이유는 마찬가지로 결국 4 앞에는 9와 4보다 작으면서 증가하는 패턴의 가장 긴 값이 메모되어 있는 것이고 같은 이유에서 3도 그렇다.
코드를 구현할 때는 이중 반복문을 숫자를 계속해서 비교해주고 비교한 숫자가 마지막이라고 가정한 숫자보다 작은 경우에는 작은 숫자의 메모 + 1 이런 식으로 해주었다.
코드에 주석을 달아두었다.
코드
TC = int(input())
for t in range(1, TC+1):
N = int(input())
# 하나의 수열을 입력 받고
arr = list(map(int,input().split()))
# 그 수열의 길이와 같이 dp리스트를 만들었다.
# 일단 모두가 적어도 1의 길이는 가지므로 1로 생성했다.
dp = [1 for i in range(N)]
# 수열의 숫자를 i로 순회하고
for i in range(N):
# 0~i까지 j로 다시 순회하면서
for j in range(i):
# i보다 앞에 있는 숫자들을 계속 비교해서 작은 것을 만나면
if arr[i] > arr[j]:
# 작은 숫자에 메모된 값 + 1, i에 메모된 값 중 큰값을 메모
dp[i] = max(dp[i], dp[j] + 1)
print('#{} {}'.format(t,max(dp)))