코딩문제풀이/Baekjoon

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

코딩하는 포메라니안 2023. 3. 1. 18:22

1. 문제

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

 

1965번: 상자넣기

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가

www.acmicpc.net

 

 

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;
    }
}

 

 

결과