[Java] 백준 1965번 : 상자넣기

1. 문제

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

1965번: 상자넣기

 

 

2. 풀이 과정

처음에는 간단하게 (해당 데이터에서 최대 길이) = (해당 데이터보다 작고 앞에 있는 것 중 가장 큰 값) + 1을 해서 이중for문으로 구현했다.

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] dp = new int[N];
        int result = 0;

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            for(int j=0; j<i; j++){
                if(arr[j] < arr[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }

        System.out.println(result+1);
    }
}

시간 제한이 큰 편이라 통과는 됐지만 더 빠른 방법이 있었다. 가장 긴 부분 수열을 이진탐색을 이용하여 구현하는 것이다.

1. 수열의 마지막 수보다 크면 size를 늘려서 넣어준다.

2. 수열의 마지막 수보다 작으면, 해당 수열에서 자신보다 작은 값 뒤에 넣어주자.

      1) 자신과 같은 값일 때는 해당 자리에 넣으면 됨

      2) 자신보다 작은 값 뒤에, 자신보다 큰 값 앞에 넣어야 함

//input
8
1 6 2 5 7 3 5 6

//process
[0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 6, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 5, 0, 0, 0, 0, 0]
[0, 1, 2, 5, 7, 0, 0, 0, 0]
[0, 1, 2, 3, 7, 0, 0, 0, 0]
[0, 1, 2, 3, 5, 0, 0, 0, 0]
[0, 1, 2, 3, 5, 6, 0, 0, 0]

이를 코드로 구현하면 아래와 같다.

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] result = new int[N+1];
        int size = 0;

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            if(result[size] < arr[i]){
                result[++size] = arr[i];
            }
            else{
                int pos = getPos(result, arr[i], size);
                result[pos] = arr[i];
            }
            
        }

        System.out.println(size);

    }

    public static int getPos(int[] result, int now, int r){
        int l = 0;
        while(l < r){
            int mid = (l + r)/2;
            if(result[mid] < now){
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        return l;
    }
}

 

 

결과