도저히 모르겠어서 구글링한 문제.. 안 봤으면 못 풀었겠는데 싶었던 문제..
삽질
- 처음에는 그냥 증가하는 수열의 마지막 수만 기억해놓고, 더 큰 수를 만날 때마다 해당 마지막 수를 업데이트해주고 count에 1을 더했다.
- 이건 내가 문제를 잘못 이해한 탓이다. 우리가 구해야 하는 건 가장 큰 증가하는 부분 수열이다.
- 즉, 증가하는 수열은 몇 개든 나올 수 있고, 그 중 길이가 가장 큰 걸 구하는 것!!
- 그래서 처음에는 2차원 배열을 만들고 열에 마지막 수를 저장할까? 했는데 이것도 노웁!
- 예를 들어 10 30 20 30 40 같은 입력이 있으면 가장 큰 증가하는 수열은 10 30 40이 아닌 10 20 30 40이다.
- 그럼 도대체 어떻게 증가하는 배열들을 각각 저장하지.. 하며 구글에 검색을 했다..
풀이
- 정답은 2중 for문이다.
- 정확히는 입력받은 수열을 다 돌면서 앞에서부터 해당 수까지 가장 크게 증가한 횟수를 저장하는 것이다.
(와 국어 진짜 못한다) - 핵심은 증가하는 부분부분 수열들을 다 저장하는 게 아니라, 해당 수 전까지 다시 또 for문을 돌면서 대소비교를 하는 것이다.
코드
import sys
input = sys.stdin.readline
N = int(input())
lst = list(map(int, input().split()))
DP = [1] * N
for i in range(N):
for j in range(i):
if lst[i] > lst[j]:
DP[i] = max(DP[i], DP[j]+1)
print(max(DP))- 주의할 점! 비교했을 때 앞의 수보다 해당 수가 더 크다고 바로 DP를 DP[j]+1로 업데이트하면 안 된다..!
- DP[i] = max(DP[i], DP[j]+1) 이렇게 안 하고 냅다 DP[i] = DP[j]+1로 적었다고 해보자.
- 그리고 예를 들어, 10 30 10 40일 때 40(i=3)일 때를 보자. j=0일 때 DP[4]=2, j=1일 때 DP[4]=3 잘 가다가 j=2일 때 DP[4]=2로 뚝 떨어진다.. 우리는 가장 크게 증가하는 길이를 찾아야 되는 거다!
- 또 하나 주의할 점! DP의 초기화값은 1이어야 한다.
i=0일 때 즉 원소가 1일 때 증가하는 부분 수열의 길이는 1이기 때문1
결과
