⭐ [백준] 11053번: 가장 긴 증가하는 부분 수열 (Java/자바)

목차

• 문제
  • 문제풀이

문제

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

 

 

문제풀이

가장 베이직한 DP 문제라고 할 수 있다. 일반적으로 DP는 이전 값을 `기억` 하는데 초점을 맞추면 된다.

memoization alogorithm 이라고 할 수 있는데 위 문제가 가장 기초가 되는 문제이다. 예제를 기준으로 설명하자면 아래와 같다.

 

1. N의 크기를 갖는 dp 배열을 생성한다.

2. dp는 0~N 까지의 index의 수열들이 갖는 최대 부분 수열을 저장할 용도이다.

3. dp는 초기에는 값을 업데이트 하지 않았기 때문에 자기 자신만을 수열로 갖는 상태이므로 1로 초기화 시켜준다.

4. [ 10, 20, 10, 30, 20, 50 ] 수열의 0 index에서 부터 N번째 index까지 순차적으로 탐색한다.

5. 탐색을 할 때 현재 index 보다 이전 index 중 현재 값 보다 작은 값을 가진 수열과 비교하여 가장 큰 수열을 찾는다.

6. 가장 큰 수열을 dp[index] 에 저장한다.

7. 4~6번 과정 반복

 

소스코드

  

    
    
    
    
  
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static int N, res;
	public static int[] arr; // 수열을 담을 배열
	public static int[] dp; // 수열의 가장 긴 부분 수열을 저장할 배열
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	N = Integer.parseInt(br.readLine());
    	arr = new int[N];
    	dp = new int[N];
        
        // 초기에는 자기 자신만을 갖는 수열이므로 1로 초기화 한다.
    	Arrays.fill(dp, 1);
    	
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	for(int i = 0; i < N; i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
        // 0~N 의 arr를 탐색한다.
    	for(int i = 0; i < N; i++) {
        	// 현재 index의 수열을 이전 index 수열을 통해 찾는다.
    		int value = dp[i];
    		for(int j = 0; j < i; j++) {
    			if(arr[j] < arr[i]) {
    				value = Math.max(value, dp[i] + dp[j]);
    			}
    		}
    		dp[i] = value;
            
            // 가장 큰 수열을 저장한다.
    		res = Math.max(dp[i], res);
    	}
    	
    	System.out.println(res);    	
    	br.close();
    }
}