11053: 가장 긴 증가하는 부분 수열 문제를 풀었었는데 한 달쯤 뒤 17216: 가장 큰 감소 부분 수열 문제를 푸니 안풀렸다. 내가 11053을 풀었던 것 조차 잊어버림.
유사문제
- 11054번. 가장 긴 바이토닉 부분 수열
- 11055번. 가장 큰 증가 부분 수열
- 11722번. 가장 긴 감소하는 부분 수열
- 12015번. 가장 긴 증가하는 부분 수열 2
- 12738번. 가장 긴 증가하는 부분 수열 3
- 14002번. 가장 긴 증가하는 부분 수열 4
- 14003번. 가장 긴 증가하는 부분 수열 5
- 1463번. 1로 만들기
1463번 1로 만들기도 LIS문제들 처럼
memoization을 1,2,3.. 순차적으로 하는데
새로운 항을 계산할 때 이전 저장값들의 일부만을 취해서 다음 항을 만들어낸다는 공통점이 있다.
문제
주어진 배열에서 우측으로 진행하는 가장 긴 증가하는 부분 수열의 길이를 찾으면 된다.
위의 예시 같은 경우는 10, 20, 30, 50으로 4가 정답이 됨.
풀이
뒤부터 슬라이싱한다. 앞에서부터 잘라도 풀이는 만들 수 있을 듯 하다.
f(i)를 i번째 인덱스 뒤로 잘랐을 때 정답이라고 하자.
여기서 f(i)는 수열을 만들 때 i번째 수를 수열에 포함한다고 간주한다.
f(5)는 1이다.
f(4)는 20을 포함한다. 그 다음 수가 50이므로 20보다 커 수열을 만들 수 있다.
50을 포함하여
f(4)=1+f(5)=2
f(3)은 30을 포함하고, 그 다음 수인 20은 30보다 작으니 건너뛴다. 50은 30보다 크니 포함한다.
f(3)=1+f(5)=2
f(2)는 최솟값이라 f(3), f(4), f(5)중 최댓값을 골라 더한다.
f(2)=1+max(f(3), f(4), f(5))=3
코드
n = int(input())
l = list(map(int, input().split()))
k = [1] * n
for i in range(n-2, -1, -1):
max1 = 1
passed = 0
for j in range(i + 1, n):
if l[j] > l[i]:
passed = 1
if k[j] > max1:
max1 = k[j]
k[i] = max1 + passed
print(max(k))k는 풀이의 f값을 적어두는 리스트이다.
