[Python] 백준(BOJ) 11053번 - 가장 긴 증가하는 부분 수열

1. 링크

https://www.acmicpc.net/problem/11053

2. 난이도(solved.ac 참고)

실버2

3. 풀이

	# https://www.acmicpc.net/problem/11053
	import sys
	f = sys.stdin.readline
	n = int(f())
	a = [int(x) for x in f().split()]
	dp = [1] * 1001
	for i in range(n):
	for j in range(i):
	if a[i] > a[j]:
	dp[i] = max(dp[i], dp[j]+1)
	print(max(dp))

view raw LIS.py hosted with ❤ by GitHub

응용이 많이 되는 유형이다. 이 문제를 먼저 접한 이유는 원래 오늘 풀기로 했던 병사 배치하기를 풀 때 필요한 부분이라고 생각되었기 때문이다. 

n까지의 범위를 가지는 i와 i까지의 범위를 가지는 j를 돌면서, 증가하는 부분 수열의 길이가 증가하려면 a[i]의 값이 a[j]보다 커야한다. 이 경우 dp의 값은 더 작은 인덱스인 j의 dp 인덱스에 1을 더해준 것과, 기존의 dp[i]의 값중에 더 큰 값이 들어가야 한다. 전자에서 +1이 들어가는 이유는 증가하는 부분수열의 길이가 1 증가했기 때문이다.