(BOJ) 상자넣기_1965번

문제

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

접근

1. 탐색

처음에는 단순히 모든 값을 탐색하면 해결될 줄 알아서 단순히 재귀로 해결하려고 했다.

코드

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

public class Main {

  static int[] arr;
  static int n;
  static int answer = 0;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    n = Integer.parseInt(br.readLine());
    arr = new int[n];
    String[] inputs = br.readLine().split(" ");

    for (int i = 0; i < n; i++) {
      arr[i] = Integer.parseInt(inputs[i]);
    }

    func(0, 1);

    bw.write(Integer.toString(answer));
    bw.flush();
    bw.close();
    br.close();
  }

  static void func(int idx, int cnt) {
    if (idx == n - 1) {
      if (answer < cnt) {
        answer = cnt;
      }
      return;
    }

    for (int i = idx; i < n; i++) {
      if (arr[idx] < arr[i]) {
        func(i, cnt + 1);
      }
    }
  }
}

결과는... 시간초과다.

2. 동적 프로그래밍

재귀로 풀었는데 시간초과라면 십중팔구 dp문제다. (적어도 본인 경험으로는)

생각해보니 앞에서부터 전부 탐색하게 되면 뒷 부분에서 반복적으로 탐색되는 부분이 존재하게 된다. 따라서 본인은 뒷부분부터 차례대로 현재 시점으로부터 본인보다 차례대로 큰 박스가 몇 개 있는지를 저장하는 dp 배열을 만들어주었다.

코드

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];
    int[] dp = new int[n];
    String[] inputs = br.readLine().split(" ");

    for (int i = 0; i < n; i++) {
      arr[i] = Integer.parseInt(inputs[i]);
      dp[i] = 1;
    }

    for (int i = n - 1; i >= 0; i--) {
      for (int j = i - 1; j >= 0; j--) {
        if (arr[j] < arr[i] && dp[j] < dp[i] + 1) {
          dp[j] = dp[i] + 1;
        }
      }
    }

    int answer = 0;

    for (int i = 0; i < dp.length; i++) {
      if (answer < dp[i]) {
        answer = dp[i];
      }
    }

    bw.write(Integer.toString(answer));
    bw.flush();
    bw.close();
    br.close();
  }
}

동작 원리는 다음과 같다.

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	1	1	1	1	1	1	1

dp 배열을 모두 1로 초기화해준다. (본인 박스를 포함한다는 의미)

지금부터 빨간색을 기준점, 파란색을 비교 대상으로 볼 예정이다.

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	1	1	1	1	1	2	1

비교 대상인 5보다 기준 값인 6이 더 크다.

즉, 기준 값이 비교 대상을 담을 수 있다.

라는 뜻이 된다. 이 때,

dp[6] vs dp[7] + 1

을 해준다. 현재 dp[6]은 본인만 해당된다(아직 초기화 상태)는 의미로 1을 갖고있고, dp[7] + 1은 본인이 현재 최대로 담을 수 있는 수(초기화 상태이므로 아직 1)에 6번째 박스까지 담겠다는 의미가 된다.

1 < 2 이므로 [6]의 값을 2로 갱신해준다. dp[6]은 본인이 제일 작은 박스이고 본인 포함 n개를 담을 수 있다는 것을 나타낸다.

한 단계 더 보면,
input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	1	1	1	1	1	2	1

비교 대상 input[5] = 3
기준 input[7] = 6

기준이 비교 대상보다 큰 상태이다. 따라서 아까와 같은 원리로 dp[5] = 2로 갱신해준다.

아직 이해하기 힘들 수 있다. 앞으로 다양한 경우를 보는 것이 좋을 것 같다.
일단 그렇게 한 바퀴 돌고나면...

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
2	1	2	2	1	2	2	1

이런 형태가 된다.

이제 두 번째 바퀴를 돌아보자.

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
2	1	2	2	1	2	2	1

이 상태로 시작하게 된다.

비교 대상 input[5] = 3
기준 input[6] = 5

기준이 비교 대상보다 큰 상태다. 위에서 스치듯 이야기한 비교하는 부분의 이유가 이제 밝혀질 예정이다.

dp[5] vs dp[6] + 1

dp[5] : 3(input[5])이 6(input[7])에 담기므로 2
dp[6] : 5(input[6])이 6(input[7])에 담기므로 2
dp[6] + 1 : 5(input[6])가 6(input[7])에 담기는데 그 5(input[6])이라는 박스에 3(input[5])를 집어넣을 예정

박스 구성 3,6 보다는 3,5,6이 더 이득이다.
따라서 dp[5] < dp[6] + 1이므로 dp[5] = dp[6] + 1로 갱신해준다.

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
2	1	2	2	1	3	2	1

이렇게 말이다.

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
2	1	2	2	1	3	2	1

비교 대상 input[4] = 7
기준 input[6] = 5

기준이 비교 대상보다 작은 상태다. 크기 5의 박스는 크기 7의 박스를 담을 수 없다. 따라서 그냥 넘어간다.

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
2	1	2	2	1	3	2	1

비교 대상 input[3] = 5
기준 input[6] = 5

기준이 비교 대상과 같다. 크기가 같아도 기준에 비교 대상 박스를 넣을 수 없다. 넘어간다.

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
2	1	2	2	1	3	2	1

비교 대상 input[2] = 2
기준 input[6] = 5


dp[2] : 2(input[2])이 6(input[7])에 담기므로 2
dp[6] : 5(input[6])이 6(input[7])에 담기므로 2
dp[6] + 1 : 5(input[6])가 6(input[7])에 담기는데 그 5(input[6])이라는 박스에 2(input[2])를 집어넣을 예정

기준이 비교 대상보다 큰 상태이다.
박스 구성 2,6 보다는 2,5,6이 더 이득이다. 따라서 dp[2] = dp[6] + 1로 갱신해준다.

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
2	1	3	2	1	2	2	1

이렇게 말이다.

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
2	1	2	2	1	3	2	1

기준점(input[6])보다 비교 대상(input[2])가 더 크므로 넘어간다.

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
2	1	2	2	1	3	2	1

기준점(input[6])보다 비교 대상(input[1])가 더 작으므로 위와 같은 원리로 dp[1] = dp[6] + 1로 갱신해준다.

이런 식으로 dp[0]이 기준점이 될 때까지 반복해서 돌려주면 된다.

예제를 가지고 다 돌리면 input 및 dp 배열은 다음과 같다.

input

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1	6	2	5	7	3	5	6

dp

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
5	2	4	2	1	3	2	1

답은 dp[0]이 된다. 박스 1, 2, 3, 5, 6으로 총 5가 된다.

간과했던 점
무조건 dp[0]이 답일 줄 알았다. 하지만 그게 아니었다.


5
4 5 1 2 3


이 입력에 대한 dp 배열은 다음과 같다.

[0]	[1]	[2]	[3]	[4]
2	1	3	2	1

아까 말했던대로라면 답은 2가 되는데, 실제 답은 3이다. 박스 1, 2, 3이 정답이기 때문이다.
따라서 dp[0]이 아닌, dp 배열에서 가장 큰 값을 가져와야 하는 것이다.