백준 11053 - 가장 긴 증가 부분 수열

Java

11053 번 - 가장 긴 증가 부분 수열

문제

접근 방법

현재 위치에서 증가 부분 수열의 합의 최대를 담는 int[] dp 배열을 선언한다.

1. 첫번재 부터 마지막의 수열을 탐색한다.
2. 현재 수열보다 앞에있는 수열들을 하나 씩 탐색한다.
3. 현재 수열보다 앞에있는 수열의 크기가 현재 수열보다 작으면,
4. 그 수열이 이전까지 담았던 최대 수열의 길이와 이전 수열 + 1을 비교하여 긴 값을 저장한다.

이를 통해서 각 수열마다, 담을 수 있는 최대 길이를 저장할 수 있다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[] arr,dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	arr = new int[n + 1];
    	dp = new int[n + 1];
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 1; i <= n; i++) {
    		arr[i] = stoi(stk.nextToken());
    	}
		// 앞에서부터 수열을 하나씩 탐색한다.
    	for(int i = 1; i <= n; i++) {
			// 현재 수 보다 앞의 수 중에서, 더 작은 수를 찾는다.
    		for(int j = i - 1; j >= 0; j--) {
    			if(arr[j] < arr[i]) {
    				dp[i] = Math.max(dp[j] + 1, dp[i]);
    				result = Math.max(dp[i], result);
    			}
    		}
    	}

    	System.out.println(result);

    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

사실 상자넣기와 동일한 문제이고,
가장 큰 증가 부분 수열에서 합을 길이로 바꾸면 푸는 문제였다.

개선할 점