🔦 문제 링크
✍️ 풀이
이 문제에 접근하는 방법은 dp를 이용하는 것이다.
그렇다면 어떻게 dp를 이용해야 할까?
수열 {10 30 10 20 20 10} 있다면 먼저 첫번째 인덱스의 감소하는 부분 수열을 구한다.
만약 4번째 20의 감소하는 부분수열을 구하게 된다면 4번째 이전 인덱스에서 4번째 인덱스보다 큰 값을 찾을 것이다. 30 -> 20 형태
이렇게 감소하는 인덱스를 찾았다면 여기서! dp를 이용해야만 한다.
30이 20으로 감소하는 인덱스이므로 그 전에 구했던 30을 가지는 인덱스가 가지는 최대길이를 이용한다.
여기서 dp의 값이 되는 것은 바로 이 최대길이이다.
즉, dp[a] = a인덱스까지 최대길이이다.
dp값은 두 가지 조건을 이용해서 구해줄 수 있다.
1. 현재 인덱스와 그 이전 인덱스를 비교했을 때 현재 값보다 더 큰 값이 있는가?
2. 만약 더 큰 값이 있다면 그 인덱스까지 최대 길이에 1을 더하면 현재 인덱스보다 커지는가?
이 두 가지 조건을 모든 인덱스의 그 이전 인덱스들에게 적용시키면 dp를 구할 수 있다.
🛠 나의 코드
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
mx = 1
for i in range(len(arr)):
dp[i] = 1
for j in range(i):
if arr[j] > arr[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
mx = max(mx, dp[i])
print(mx)📝 정리
이 문제 c++,java,python 3개로 4번이나 풀었었는데 전혀 감을 못잡았다...
풀기만 하는게 중요한게 아니라 어떻게 푸는지 정확히 기억해야 할 것 같다..
🎈 참고
Go Go