백준 1965) 상자넣기 Java 자바

문제

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

정답

 숫자의 순서를 유지하며 값이 증가하는 수열을 찾아야 하므로 LIS + dp 를 이용하여 풀었다.

각 위치에서 가능한 이전 값들과 비교하여 dp 배열을 업데이트 한다.

 

코드를 보며 확인해보자.

 

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

// https://www.acmicpc.net/problem/1965
public class Main {

    static int [] box, dp;
    static int N;

    public static int solution(int n){
        dp = new int[n];
        Arrays.fill(dp,1);
        for (int i = 0 ; i < box.length; i++){
            for (int j = 0 ; j < i ; j++){
                if (box[j]<box[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        box = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0 ; i < N ; i ++){
            box[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(solution(N));
    }
}