[백준/1965] 상자넣기 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버2
출처 : 백준 - 상자넣기

🦧 문제 풀이 접근

2중 for문을 이용해서 dp를 풀어나간다.
배열의 앞에서부터 dp 배열에 '현재 위치까지 최대로 넣을수 있는 상자의 갯수'를 저장한다.
앞선 숫자중 현재 숫자보다 작은 숫자중에 dp 배열의 값이 최대인 숫자+1 값을 저장한다.

💻 code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        int max = 0;
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<n;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=0;i<n;i++) {
            dp[i] = 1;
            for(int j=0;j<i;j++) {
                if(arr[j] < arr[i] && dp[j]+1>dp[i])
                    dp[i] = dp[j]+1;
            }
            max = Math.max(dp[i],max);
        }

        System.out.println(max);
    }
}

🥇 결과

🎓 느낀점

2중 for문을 사용하지 않고 풀려했으나 실패했다.
간단한 dp문제다.