백준 1965 - 상자넣기

Java

1965 번 - 상자넣기

문제

접근 방법

현재 상자가 가질 수 있는 최대의 값을 담는 int[] dp 배열을 선언한다.

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

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

코드

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

public class Main {
	static int n, result;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	stk = new StringTokenizer(br.readLine());

    	int[] arr = new int[n + 1];
    	int[] dp = new int[n + 1];

    	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[i] > arr[j]) {
    				dp[i] = Math.max(dp[i], dp[j] + 1);
    			}
    		}
    		result = Math.max(result, dp[i]);
    	}

    	System.out.println(result);

    	br.close();
	}

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

총평

후기

개선할 점