문제
https://www.acmicpc.net/problem/11053
소스코드
if __name__ == "__main__":
n = int(input())
arr = list(map(int,input().split()))
dp = [0] * n #메모이제션을 0으로 초기화한 경우
for i in range(n):
for j in range(i):
if arr[i] > arr[j] and dp[j] > dp[i]:
dp[i] = dp[j]
dp[i] +=1
print(max(dp))소스코드 2
if __name__ == "__main__":
n = int(input())
arr = list(map(int,input().split()))
dp = [1 for _ in range(n)] #메모이제이션을 나포함 1로 초기화
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[j]+1,dp[i])
print(max(dp))설명
- for i in range(n): for j in range(i):
주어진 수열을 하나씩 선택해서 선택한 수열 밑에 값이 작은게 몇개나 있는지 체크한다. - if arr[i] > arr[j] and dp[j] > dp[i]
선택한 수열의 값이 무조건 커야하고 & 조건으로 누적된 값이 현재 체크하는 수열 값의 누적값 (dp[i]) 보다 크면 그 값을 채택한다. (꾸준히 증가했다는 뜻임) - dp[i]+=1
나 자신을 포함해야하므로 1을 무조건 더해준다. (감소하는 수열이면 dp[i]는 1이 된다.)
아래 그림을 참고해서 예를 들어보자
i = 3 일 때 arr[i] = 30 이다
j = 0 일 때 arr[0] = 10 이고, 30 > 10 이니 조건을 충족하고 누적된 값 1 > 0 이므로 증가수열이기 때문에 dp[3]에 dp[0]의 누적 값을 넣어준다.
j = 1 일 때 arr[1] = 20 이고, 30 > 20 이니 조건을 충족하고 누적된 값 2 > 0 (10,20) 이므로 증가수열이기 때문에 dp[3]에 dp[1]의 누적 값을 넣어준다.
j = 2 일 때 arr[2] = 10 이고, 30 > 10 이니 조건을 충족한다. 하지만 누적된 값 1 > 2 이므로 증가수열이 아니기 때문에 패스한다.
마지막에 dp[3]에 + 1 을 해줘서 자기 자신이 혼자있다고 가정해서 증가처리해준다.
후기
처음에 memo = 0 이라고 변수를 설정하고 첫번째 원소부터 탐색해서 memo 보다 크면 memo를 변경해주고 cnt를 계산하는 방식으로 풀었다. 이렇게 하면 예제는 맞지만 부분수열을 탐색한게 아니라서 실패했다.
부분수열의 의미를 잘 파악하자 그냥 중간부터 탐색할 수 도 있다
