본문 바로가기
백준

[백준] 알고리즘 분류(다이나믹 프로그래밍,JAVA)1965번, 상자넣기

by 열정적인 이찬형 2023. 2. 20.

문제 링크

 

1965번: 상자넣기

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

www.acmicpc.net


주의사항

  • JAVA를 사용하여 프로그램을 사용하였습니다.
  • 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{ 	
	public static void main(String[] args){
    }
}

문제 설명


접근 방법

이 문제에 핵심

 

1. 상자는 뒤에 자신보다 큰 상자가 존재할 때 넣을 수 있습니다.

2. 상자는 일렬로 정렬되어 존재합니다.

3. 한 번에 넣을 수 있는 최대의 상자 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. LIS를 이용해서 DP[]를 구성하도록 탐색합니다.

 

3. 탐색이 끝나고 DP[]의 최대 값을 결과로 출력합니다.

 

상자 탐색!

 

이 문제에 설명을 살펴보면 박스를 다른 박스에 놓았을 때 해당 박스보다 작은 박스는 넣을 수 없습니다.

 

Top View 시점에 현재 박스 상황을 가정하면

빨간색 상자는 넣을 수 없습니다.

Why? 그보다 작은 상자가 이미 들어가 있기 때문입니다.

내용 해석 : 수가 점점 증가 박스의 최대 개수를 구해라!

 

LIS 동일한 내용!

 

최장 증가 부분 수열 - 나무위키

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.

namu.wiki

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 8

1 6 2 5 7 3 5 6

 

2. LIS를 이용해서 DP[]를 구성하도록 탐색합니다.

 

LIS를 이용한 DP[] 구성

 

  1 6 2 5 7 3 5 6
DP 1 0 0 0 0 0 0 0

0번째 인덱스 1이 마지막일 때에는 넣을 수 있는 상자가 없으므로 1으로 초기화를 해줍니다.

 

1 6 2 5 7 3 5 6

 

  1 6 2 5 7 3 5 6
DP 1 2 0 0 0 0 0 0

DP[1] = DP[0] + 1 = 2

 

1 6 2 5 7 3 5 6

 

  1 6 2 5 7 3 5 6
DP 1 2 2 0 0 0 0 0

DP[2] = DP[0] + 1 = 2

 

1 6 2 5 7 3 5 6

 

  1 6 2 5 7 3 5 6
DP 1 2 2 3 0 0 0 0

DP[3] = DP[2] + 1 = 3

 

1 6 2 5 7 3 5 6

 

  1 6 2 5 7 3 5 6
DP 1 2 2 3 4 0 0 0

DP[4] = DP[3] + 1 = 4

 

1 6 2 5 7 3 5 6

 

  1 6 2 5 7 3 5 6
DP 1 2 2 3 4 3 0 0

DP[5] = DP[2] + 1 = 3

 

1 6 2 5 7 3 5 6

 

  1 6 2 5 7 3 5 6
DP 1 2 2 3 4 3 4 0

DP[6] = DP[6] + 1 = 4

 

1 6 2 5 7 3 5 6

 

  1 6 2 5 7 3 5 6
DP 1 2 2 3 4 3 4 5

DP[7] = DP[6] + 1 = 5

 

 

3. 탐색이 끝나고 DP[]의 최대 값을 결과로 출력합니다.

 

  1 6 2 5 7 3 5 6
DP 1 2 2 3 4 3 4 5

 

5 결과로 출력합니다.

 

  • BufferedReader를 사용하여 입력되는 정보를 저장합니다.
  • StringTokenizer를 이용하여 상자 정보를 띄어쓰기 기준 나누었습니다.
  • LIS를 통해서 DP를 구성하였습니다.
  • DP[]의 최대값을 결과로 System.out.printf를 통해 출력하였습니다.

 

결과코드

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] rooms;	//박스 정보
    static int[]DP;		//LIS를 이용해서 저장할 메모이제이션
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        rooms = new int[N];
        DP = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //Box정보 저장
        for(int i=0;i<N;i++)
            rooms[i] = Integer.parseInt(st.nextToken());

        //LIS를 통해 DP 구성!
        for(int i=0;i<N;i++){
            DP[i] = 1;	//상자 자신 개수 + 1
            //자신보다 앞에 있는 작은 상자들 탐색
            for(int j=0;j<i;j++){
                if(rooms[i] > rooms[j])
                    DP[i] = Math.max(DP[i], DP[j] + 1);
            }
        }
        int result = 0;
        //DP의 최대값 구하기!
        for(int i=0;i<N;i++)
            result = Math.max(result, DP[i]);
        System.out.print(result);		//결과 출력

    }
}

댓글