11053 가장 긴 증가하는 부분 수열
[ tip ]
input을 sys.stdin.readline 으로 선언해놓으면, 귀찮게 저렇게 다 안치고 input()으로만 쳐도 sys.stdin.readline을 친 것과 같은 효과를 볼 수 있다. 속설에 따름녀 sys.stdin.readline은 input보다 속도가 거의 2배 빠르다고 하므로 ... 저렇게 써서 하는 것이 좋아보인다.
LIS 문제였는데, dp는 A[i]에서 가장 긴 부분수열의 길이를 넣어놓는다. 10 20 10 30 20 50 이라고 할 때 dp값은 다음과 같다.
| A | 10 | 20 | 10 | 30 | 20 | 50 |
| dp | 1 | 2 | 1 | 3 | 2 | 4 |
생각보다 단순할 수 있는데, 처음에는 생각하기 어렵다. A[i]에서 자기 앞에 자기보다 작은 수가 몇개인지 세면 됐기 때문이다. dp는 자기 자신이 몇번째 순서인지를 나타낸다. dp값이 2라면 자기보다 작은 값이 내 앞에 1개가 있고 자기가 그 바로 다음인 2번째 순서라는 의미이다.
이것을 코드로 나타내면 일단 dp는 자기 자신을 포함하므로 모두 1로 초기화해주고 N개만큼 선언해준다.
그리고 이중for문으로 자기 앞에 있는 수들과 비교하는 작업을 거쳐주는데, 이것은 많이 나오는 구조이므로 익숙할 것이다. 안쪽에 있는 for문에서 i번째까지만 돌면 각 element마다 처음부터 element의 바로 전까지 비교하는 작업을 거쳐주게 된다. 여기선 if문이 가장 중요한데, dp값이 늘어나는 경우는 내가 이전 값보다 클때만 늘어난다. 그렇기 때문에 A[i] > A[j]일 때를 if문의 참으로 둔다.
예를 들어 10 20 10 30인 경우에 일단 dp는 다 1이고 20은 곧 2로 바뀐다. 3번째 10은 애당초 큰게 없으니 그대로 1인데 그럼 30은 어떻게 되느냐? 30은 20과 비교했을 때 3으로 바뀌는데, 다음을 보자. 30인 경우 10 20 10과 각각 한번씩 비교를 하는데 10보다 크므로 일단 30은 2가 된다. 그럼 20과 비교를 해야하는데 이미 20의 dp값은 2이다. dp[ j ]+1과 비교해야 하므로 30은 20과 비교할 때 자신의 dp값인 2와 20의 dp값인 2에서 1더한 3을 비교해서 큰 값을 30에 넣는다. 그렇기 때문에 30의 dp값은 3이 된다. 그 다음 다시 10과 비교할 때, 자신의 dp값인 3과 10의 dp값 1에서 1을 더한 2와 비교했을 때 3이 크기 때문에 dp값의 변화 없이 그대로 3이 유지된다. 이런식으로 dp값이 채워지게 되고, 가장 큰 dp값을 print해주는 것이 바로 가장 길게 증가하는 부분수열 LIS가 된다.
import sys
input = sys.stdin.readline # 더 간결하게 sys.stdin.readline()을 사용하는 방법
N = int(input())
A = list(map(int, input().split()))
#########
dp = [1] * N
for i in range(1,N):
for j in range(i):
if A[i] > A[j]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
언제나 그렇듯, 점화식을 생각하기가 참 어렵다. dp에서 점화식은 보통 max ~~ min ~~ 처럼 최대 최소 함수를 이용하여 많이 나오므로 항상 그런 경우를 염두해두자.
