11054

백준 11054 풀이 (가장 긴 바이토닉 부분 수열, 다이나믹 프로그래밍)

이번에는 저번 시간에 풀었던 11053을 응용한 문제를 풀어보자. 처음 보면 솔직히 나야 역시나 무슨 말인지 몰라서 2~3번은 더 읽어보았다. 간단히 요약하자면 S1 Sk+1 > ... SN-1 > SN 과 같은 수열의 형태인 바이토닉 부분 수열을 찾되 가장 긴 부분 수열을 찾아보자는 것이다. 11053번에서 나는 오름차순으로 가장 긴 부분 수열을 찾을 수 있었다. 11054는 내림차순을 구해보라는 문제이다. 일단 문제를 풀기에 앞서 표를 그리며 생각해본다. number 1 5 2 1 4 3 4 5 2 1 dp (->) 1 2 2 ... ..... ... 4 5 2 1 dp2 ( dp[target]: dp[target] = dp[i] + 1 target2 = le..