반응형
백준11722번
-
[백준 11722번] 가장 긴 감소하는 부분 수열 Java 풀이문제풀이/백준 2021. 9. 28. 12:13
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP를 이용하여 문제를 풀었습니다. 이번 문제의 목적인 가장 긴 감소하는 부분 수열을 구하는 것이므로 부분 수열의 최대 길이를 DP에 메모라이즈 하여 문제를 풀 수 있습니다. 만약 입력으로 N = 1, 입력 수로 10이 주어 지면 DP[0] = 1이고 정답 또한 1이 될 것입니다. 이번에는 N = 2, 입력 수로 10, 30이면 어떻게 될까요? 먼저 N이 어떤 수가 입력으로 주어지더라도 DP[0]은 무조건 1일 될 것입니다. 최초의 수는 시작하는 수이므로 길이가 1이 되기 때문입니다. 그럼 DP[1]은 ..