99클럽 코테 스터디 28일차 TIL: LIS 응용

문제

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

풀이

어제 풀었던 문제에서 약간만 응용하면 쉽게 풀 수 있는 문제이다.

dp값을 초기화 하는 것은 자기 자신의 값으로 초기화 해주자.
=> 자기 자신도 부분수열이 될 수 있기 때문

이중 for문을 돌면서 이전 원소보다 크다면 내 원소를 붙일 수 있는 것을 기억하자.
코드는 어제 푼 것과 거의 동일하다.

소스코드

	let n = Int(readLine()!)!
	let array = readLine()!.split { $0 == " " }.map { Int($0)! }
	var dp = array
	for i in 0..<n {
	for j in i..<n {
	if array[j] > array[i] {
	dp[j] = max(dp[j], dp[i] + array[j])
	}
	}
	}
	print(dp.max()!)

view raw 11055_가장 큰 증가하는 부분 수열.swift hosted with ❤ by GitHub

후기

전날 풀었던 문제와 거의 유사해서 쉽게 풀 수 있었다.