[백준] 1965번 : 상자넣기 - 자바(JAVA)

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

1965번: 상자넣기

문제 해석

상자가 일렬로 늘어서 있는데 상자마다 크기가 존재한다.

앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있다.

만약 상자의 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 존재한다면, 크기 1인 상자를 크기 5인 상자에 넣고 크기 5인 상자를 크기 7인 상자 안에 넣을 수 있다.

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하라.

위의 예시의 경우에는 3

---

입력

첫번째 줄은 상자의 개수 n

두 번째 줄에는 각 상자의 크기가 순서대로 주어진다.

 

제약조건

1 <=n <=1,000

---

출력

넣을 수 있는 최대의 상자 개수를 출력한다.

---

문제 풀이 전 설계

임의의 입력값을 두고 생각해 보자

 

만약 시작 값을 기준으로 가장 작은 값으로 이동하는 것은 문제가 생길 수 있다.

4
1 3 4 2

만약 시작 값 1을 기준으로 그다음 작은 값인 2로 이동하게 되면 최대값이 2로 측정되지만 사실 1,3,4 를 하게되면 최댓값을 3이다.

 

 

숫자마다 자신보다 우측에 존재하는 큰 값을 개수를 저장하여 이를 이용하자

8
1 6 2 5 7 3 5 6

 

위와 같은 상자의 크기 순서대로 자신보다 우측에 존재하는 큰 값의 개수를 저장한다면 ( 오른쪽으로 밖에 넣을 수 없기 때문에)

7 1 5 2 0 2 1 0의 크기를 가집니다. 그러면 7 -> 5 -> 2 -> 1 -> 0 순으로 자신보다 큰 값의 개수의 순서가 큰 값을 우선으로 이동한다면 1 -> 2 -> 3 -> 5 -> 6으로 이동하여 최댓값을 가질 수 있습니다.

 

만약 큰 값의 개수가 같다면 현재 값보다 큰 값 중 더 작은 값으로 이동합니다. ( 5와 3중에는 3이 더 작음)

 

다른 예제로도 한번 살펴보겠습니다.

10
1 7 8 9 10 11 2 3 4 6

숫자 마자 자신보다 우측에 존재하는 큰 값의 개수를 저장합니다.

9 4 3 2 1 0 3 2 1 0

따라서 9 -> 4 -> 3 -> 2 -> 1 -> 0 순으로 자신보다 큰 값의 개수의 순서가 큰 값을 우선으로 이동한다면 1 -> 7 -> 8 -> 9 -> 10 -> 11으로 이동하여 최댓값을 가질 수 있습니다.

이때 우선순위가 동일하다면 현재 값보다 큰 값 중 작은 값으로 이동합니다. (7보다 큰 값 중은 8밖에 존재하지 않음)

 

혹시나 반례가 존재하는지 확인하기 위해 더 살펴보겠습니다.

10
1 7 8 9 10 2 3 4 6 7

 

9 3 2 1 0 4 3 2 1 0

9 -> 3 ->2 ->1 -> 0으로 이동한다면 5개의 값을 가지며

9 -> 4 -> 3 -> 2 -> 1 -> 9으로 이동한다면 6개의 값을 가집니다.

 

8
1 4 2 3 1 2 3 4

6 0 2 1 3 2 1 0

1 -> 2 -> 3 -> 4로 이동

 

5
6 7 8 9 1 2 4 3

3 2 1 0 3 2 0 0

1 -> 2 -> 3 or 4로 이동

6 -> 7 -> 8 ->9 가 최댓값을 가지므로 반례 발생

 

 

도저히 감이 오지 않아 다른 분들의 풀이를 찾아봤습니다.

LIS라는 최장 증가수열과 DP 알고리즘을 사용해야 합니다.

단순히 다음 큰 수로 이어지주는것이 아니라 작은수 -> 큰수로 이어 줄 때 이을 수 있는 최대 개수를 구해야 합니다.

 

arr[] = {10, 20, 10, 30, 20, 50}

 

위의 배열에 대하여 dp []를 만들어 줍니다.

dp [i] = i번째 수까지 증가하는 최대 수의 개수 = 우리가 찾고자 하는 정답

 

dp [1] = 1번째 수까지 증가하는 최대 개수는 자기 자신밖에 없으므로 1입니다.

dp [2] = 2번째 수까지 증가하는 최대 개수는 2입니다.

dp [3] = 3번째 수까지 증가하는 최대 개수는 1입니다.

 

직관적으로 위와 같이 알 수 있으며, 이를 통해 규칙성을 파악해보겠습니다.

우선 30이라는 값은 앞선 원소들(10, 20, 10)에 비해 큰 값입니다.

즉, 어떤 원소가 오더라도 해당 원소 뒤에 추가되면서 최장 증가 부분 수열이 증가될 수 있음을 나타냅니다.

우리가 dp [i]에 저장한 값은 해당 원소의 위치에서 가질 수 있는 LIS의 길이입니다.

즉, 해당 위치에서 앞 원소들에 비하여 증가할 가능성이 존재한다면( a [j] < a [i] ), 해당 위치의 LIS의 값에 자신의 길이를 +1해 주면 된다는 것을 알 수 있습니다. ( d [i] = d [j] + 1)

 

자신의 길이를 1로 채우는 경우(초기화)부터 생각해보겠습니다.

 

초기화 이후에 첫 번째 원소(10)에 대하여 30이라는 값이 더 크기 때문에 부분 수열의 길이를 증가시킬 수 있으므로 dp [1] + 1의 값을 dp [4]의 후보에 올릴 수 있습니다.

마찬가지로 2, 3 번째 원소(20, 10)에 대하여 30이라는 값이 더 크기 때문에 부분 수열의 길이를 증가시킬 수 있으므로 dp [2] + 1 , dp [3] + 1의 값을 dp [4]의 값 후보에 올릴 수 있습니다.

이중에 가장 큰 값은 무엇일까요? 2번째 원소의 최장길 이수 열인 dp [2] + 1 의값인 3입니다.

따라서 해당 위치의 값은 3이 됩니다.

다음으로는 5번째 원소인 20에 대하여 생각해보겠습니다. 앞의 논리를 그대로 적용시키면 됩니다.

초기값은 1로 설정합니다. ( 자기자신이 가장 큰 경우에는 최장 길이 수열이 1이기 때문에 최솟값이 1이므로 1으로 설정)

20이라는 값의 앞에 존재하는 원소(10, 20, 10, 30,)에 대하여 20보다 작은 값들만 수열의 길이가 증가할 가능성이 있습니다. ( 원소들이 10인 경우만 가능!)

따라서 해당 위치의 LIS의 값에 +1을 한 값들만 후보에 올라갈 수 있습니다.

여기서 가장 큰 값은 2이며, 해당 위치의 LIS값은 2가 됩니다.

위와 같은 방법으로 마지막 원소를 채우게 되면 dp [6]에는 4라는 값이 들어갑니다.

 

 

위의 생각을 구현한 핵심 로직은 아래와 같습니다.

for (i = 1; i <= n; i++) {
		d[i] = 1; //1로 초기화
		for (j = 1; j < i; j++) {
			if (a[j] < a[i] && d[i] < d[j] + 1) { //핵심 LIS 방식
				d[i] = d[j] + 1;
			}
		}
		if (max < d[i]) max = d[i]; //그때그때마다 비교해서 max에 저장
	}

d [i] = 1으로 초기화하는 이유는 만약 a [i] = {5, 5, 5, 5, 5}라면 즉, 자기 자신보다 작은 수들이 없으면 d [i]의 값은 1입니다.

 

현재 index의 상자 크기보다 앞의 index의 상자 크기가 더 작으면 앞의 index의 상자 dp값 + 1 이 현재 dp값보다 크면 변경해준 뒤 max값을 현재 dp값이랑 비교해서 변경해준다

 

 

어떤 자료구조를 사용할까?

상자의 개수 n을 입력받다 보니 크기가 정해진 배열을 사용하면 될 것 같다.

---

어려웠던 점

LIS라는 최장 증가수열과 DP 알고리즘을 활용해야 했다.

DP라고 한다면 이전에 구했던 값들을 통해 다음 값을 구한다고 이해하고 있어서 전에 구했던 값들을 한 번만 쓰면 된다고 생각했지만 2중 반복문을 통해 계속 값을 사용할 수 있다는 것을 알게 되었습니다.

 

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class InputBox {
	static int[] boxArray;
	static int[] dp;
	static int n;
	static int maxBoxCount;

	public static void main(String[] args) throws IOException {

		inputBoxData();
		calculateMaxBoxCount();
		printMaxBoxCount();

	}

	private static void inputBoxData() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		boxArray = new int[n + 1];
		dp = new int[n + 1];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= n; i++) {
			boxArray[i] = Integer.parseInt(st.nextToken());
			dp[i] = 1;
		}

		br.close();
	}

	private static void calculateMaxBoxCount() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				if (boxArray[i] > boxArray[j] && dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
				}
			}
			maxBoxCount = maxBoxCount > dp[i] ? maxBoxCount : dp[i];
		}
	}

	private static void printMaxBoxCount() throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(maxBoxCount + "\n");
		bw.flush();
		bw.close();

	}

}

위의 로직을 이해하셨다면 위의 코드는 이해하기 쉬울 것입니다!

 

 

 

https://sskl660.tistory.com/89

[Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence)