백준 11053 - 가장 긴 증가하는 부분 수열(자바 - 동적 프로그래밍)

백준 11053 - 가장 긴 증가하는 부분 수열(자바 - 동적 프로그래밍)

평범한 배낭 문제 이후 또 다시 마주친 동적 프로그래밍 응용 문제

위의 말에서 언급한 평범한 배낭 문제와 같이 또 한번 동적 프로그래밍의 역량 부족을 느낀 문제이다.

실버 2 라는 문제 난이도를 보고 그래도 쉽지 않을까 생각했으나 동적 프로그래밍 방식의 코딩에 대한 역량 부족은 문제의 난이도와는 별개였다.

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

입력으로 수열의 데이터가 들어왔을때, 해당 수열의 값이 증가하는 부분 수열 중에서 가장 길이가 긴 수열의 길이 값을 반환하는 문제이다.

처음 이 문제를 풀 때는 그냥 일단 수열을 정렬한 다음, 중복되는 숫자들을 제거 해주면 그게 바로 가장 긴 증가하는 부분 수열이 아닌가 생각하고 코딩을 해봤지만 언제나 그렇듯 그건 틀린 생각이었다.

결국 이 문제도 패스트 캠퍼스의 해설 강의를 참조하게 되었다.

진짜 동적 프로그래밍은 조금만 문제가 응용되서 나와도 도대체 점화식을 어떻게 짜야 할지 도통 감이 오질 않는것 같다.

핵심 아이디어

- D[i] = array[i] 를 마지막 원소로 가지는 부분 수열의 최대 길이를 구한다.

- 모든 0 <= j < i 에 대하여 D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

- Main.java

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class Main { // 전형적인 동적 프로그래밍 문제 // 수열의 크기가 N일 때, 기본적인 동적 프로그래밍 알고리즘으로 O(N^2) 에 해결할 수 있다. /* * D[i] = array[i] 를 마지막 원소로 가지는 부분 수열의 최대 길이 * 모든 0 <= j < i 에 대하여, D[i] = max(D[i], D[j]+1) if array[j] < array[i] */ public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int arraysize = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int[] array = new int[arraysize]; for(int i = 0; i < arraysize; i++) { array[i] = Integer.parseInt(st.nextToken()); } int[] dp = new int[arraysize]; for(int i = 0; i < dp.length; i++) { dp[i] = 1; } for(int i = 1; i < arraysize; i++) { for(int j = 0; j < i; j++) { if(array[j] < array[i]) dp[i] = Math.max(dp[i], dp[j]+1); } } bw.write(Arrays.stream(dp).max().getAsInt() +"

"); bw.flush(); bw.close(); } }

from http://evan-development.tistory.com/154 by ccl(A) rewrite - 2021-12-26 20:01:57