[BAEKJOON]1965 상자넣기

문제 요약

• 알고리즘 분류: dp, LIS
• 난이도:  Silver2
• 문제내용:
  • 상자가 일렬로 있다. 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다.
  • . 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다.
  • 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.
  • 상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

• 사이트: https://www.acmicpc.net/problem/1965

문제풀이

 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 LIS 개념을 적용해서 풀어야 한다. LIS에 대한 개념은 아래 글에서 확인 해보면된다.

https://jih3508.tistory.com/46

[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

이번 문제에서  앞에 순서대로 큰 상자를 넣는다는 점에서 최장 증가하는 수열을 구하는 문제랑 비슷하다. 그래서 LIS 기본 개념에서 그대로 구현해서 따로 설명 안하겠다. 

Code

 LIS중 데이터 양이 최대 1000개라서 DP로 풀수 있어서 간단하게 DP로 했다.

Python

N = int(input())
BOX = list(map(int, input().split()))
dp = [1] * N

for i in range(1, N):
    for j in range(i):
        if(BOX[i] > BOX[j]):
            # 이전 값들과 비교해서 큰 값이면 이전 저장 되는 것과 수열 개수 비교
            dp[i] = max(dp[i], dp[j] + 1)

# dp 배열중 가장 길게 저장 된 결과 값을 가져온다.
print(max(dp))

Java

import java.util.*;
import java.io.*;

public class Main {

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

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

		Arrays.fill(dp, 1);
		for (int i = 1; i < N; i++) {
			for (int j = 0; j < i; j++) {
				// 이전 값들과 비교해서 큰 값이면 이전 저장 되는 것과 수열 개수 비교
				if(BOX[i] > BOX[j]){
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}

		// dp 배열중 가장 길게 저장 된 결과 값을 가져온다.
		System.out.println(Arrays.stream(dp).max().getAsInt());

	}
}