기본적인 DP 문제이다.
처음에 문제를 제대로 이해하지 못해서, 단순히 주어진 리스트에서 중복을 제거하고, 오름차순 정렬한게 답이라고 생각했다.
하지만 이 문제는 증가하는 '부분'수열이 핵심이다.
즉, 주어진 리스트 그대로 그 안에서 오름차순으로 진행되는 부분적인 수열을 의미한다.
예를 들어서 설명해보겠다.
주어진 리스트 수열이 [5, 1, 6, 2, 7, 3, 8] 라고 가정할 때, 리스트 내의 한 수를 잡고, 그 뒤로 나오는 값들을 비교하면서 오름차순 수열을 만드는 것이다.
- 5를 잡았을때, [5,6,7,8] 이 하나의 증가하는 부분 수열이 된다.
- 1을 잡았을때, [1,2,3]이 하나의 증가하는 부분 수열이 된다.
즉, 이런식으로 증가하는 부분수열을 찾아서 제일 길이가 긴 것을 출력하면 되는 문제이다.
접근방법
그럼 코드를 어떻게 접근해야 하는 것일까?
우선 위의 설명처럼 숫자 하나를 잡고, 그 뒤의 숫자를 탐색하면서 증가하는 부분수열을 찾아야겠다고, 생각을 할 것이다.
하지만, 그렇게 코드를 작성할 때 생기는 문제점이 있다.
예로 주어진 리스트가 [1, 3, 4, 2, 3, 4] 라고 칠 때, 1을 잡고 증가하는 부분 수열을 찾으면,
[1,3,4], [1,2,3,4] 이렇게 두개가 나온다. 이처럼 잡은수를 가지고 두번 혹은 그 이상을 돌려야 완벽히 부분 수열을 찾을 수 있다. 하지만, 그런 부분수열이 몇개가 나올지 모른다.
그래서 DP를 이용해서, 잡은 숫자와 그 이전의 숫자의 DP배열의 값을 비교해서 문제를 풀어볼 것이다.
코드
n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(n)]
for i in range(n):
for j in range(i):
if a[i] > a[j] and dp[i] < dp[j]:
dp[i] = dp[j]
dp[i] += 1
print(max(dp))- dp를 0으로 초기화 한다.
- 첫번째 for문은 값을 지정하는 역할, 두번째 for문은 지정한 값 이전의 값들과 비교하는 역할
- 두번째 for문 내의 a[i]>a[j] 는 주어진 배열에서 현재 지정한 값이 그 이전 값들보다 커야하고,
dp[i]<dp[j] 는 현재 dp의 값이 이전 dp의 값보다 작을 경우에만 현재 dp에 이전 dp의 값이 저장된다. - 그렇게 두번째 for문이 다 돌면, dp[i] 에는 0 혹은 i이전의 j중 dp값이 젤 큰 dp[j]의 값이 들어있다.
- 그러고 dp[i]에 1을 더해주면, 완성이다.
Backend Developer