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

문제 링크

1965번: 상자넣기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

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

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

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

 

알고리즘 진행 순서.

 

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

 

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

 

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

 

상자 탐색!

 

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

 

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

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

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

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

 

LIS 동일한 내용!

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

 

예제입력 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);		//결과 출력

    }
}