99클럽 코테 스터디 30일차 TIL DP(상자넣기)

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

문제 읽으면서 든 생각. 어라..? 이거 그냥 가장 긴 증가하는 부분수열 아닝가..?

https://www.acmicpc.net/problem/11053 (백준 11053 가장 긴 증가하는 부분 수열)

 

<아이디어>

크기가 더 큰 상자에 크기가 더 작은 상자를 넣을 수 있고, 이렇게 넣을 수 있는 최대 상자의 개수를 구하는 문제.

결국은 오름차순을 가지는 수열의 개수를 구하면 되는 문제이다.

예제를 살펴보면 1 6 2 5 7 3 5 6 -> 1, 2, 3, 5, 6 으로 총 5개가 답이 된다.

순차적으로 배열을 탐색하며 현재 값보다 인덱스가 작은(이전에 위치한) 값들을 보며 현재 값보다 작으면 해당 인덱스 dp에 + 1 씩 하며 최댓값을 갱신해준다.

 

 

<제출코드>

package Study.Week05;

/*
오름차순 최대 길이..?
 */

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

public class Day30_BOJ_1965_상자넣기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[n];
        Arrays.fill(dp, 1);		// 전체 값 1로 초기화 (자기 자신 길이)
        int ans = 1;			// 답의 최솟값은 1 (자기 자신 길이)
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
            	// 나보다 이전 값이 더 작으면 (오름차순 이면)
                if(arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}