백준 2240번 자두나무 [DP] :: 마이구미

이번 글은 백준 알고리즘 2240번 "자두나무" 를 다뤄본다.

이 문제의 풀이는 동적계획법으로 해결한다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

문제는 크게 세가지의 키워드로 분류할 수 있다.

자두가 떨어지는 T초, 최대 움직일 수 있는 W번, 자두가 위치할 수 있는 위치번호(1, 2번)

문제의 예제처럼 t = 7초, w = 2번의 입력이 주어졌다고 보자.

7 2 => 2 1 1 2 2 1 1

입력의 예제를 그림으로 나타내면 아래와 같다.

여기서 우리는 어떻게 점화식을 도출할 수 있을까?

3가지 키워드로 분류했으니 DP 배열을 3차원 배열로 만들어보자.

dp[자두나무 위치][떨어지는 시간][최대 움직일 수 있는 횟수]
dp[L][T][W]

위와 같이 DP 배열을 만든 후 자두를 받을 수 있는 경우를 생각해보자.

2가지를 생각할 수 있다.

• 움직이지 않고 같은 위치에서 다음 자두를 받는 경우.
• 움직여서 다른 위치의 자두를 받는 경우.

최대 자두 개수를 구하는 문제이기에, 2가지 경우 중 비교하여 값이 큰 경우를 구하면 된다.

그림으로 나타내면 아래와 같다.

위 그림처럼 자두를 받을 수 있는 2가지의 경우를 활용해 점화식을 도출할 수 있게 된다.

// 자두가 1번 자두나무에 떨어질 경우.
dp[1][T][W] = MAX(dp[1][T-1][W] + 1, dp[2][T-1][W-1] + 1)

// 자두가 2번 자두나무에 떨어질 경우.
dp[2][T][W] = MAx(dp[2][T-1][W] + 1, dp[1][T-1][W-1] + 1)

T의 경우는 이전의 경우의 값을 사용하기 때문에 T-1이 되는 것이고,

W의 경우는 움직여서 다른 위치의 자두를 받는 경우는 움직였다는 의미임으로써, W-1이 되는 것이다.

이 점화식을 활용해 주어지는 자두 위치를 구분하여 코드를 작성함으로써, 문제를 해결 할 수 있다.

for (int i = 1; i <= t; i++) {
    for (int j = 1; j <= w + 1; j++) {
        if (arr[i] == 1) {
            dp[1][i][j] = Math.max(dp[1][i - 1][j] + 1, dp[2][i - 1][j - 1] + 1);
            dp[2][i][j] = Math.max(dp[1][i - 1][j - 1], dp[2][i - 1][j]);
        } else {
            if (i == 1 && j == 1) {
                continue;
            }
            dp[1][i][j] = Math.max(dp[2][i - 1][j - 1], dp[1][i - 1][j]);
            dp[2][i][j] = Math.max(dp[1][i - 1][j - 1] + 1, dp[2][i - 1][j] + 1);
        }
    }
}

else 문에서 조건은 처음 시작했을 때, 2번에 있는 자두를 먹기 위해 움직이는 경우를 위함이다.

두번째 반복문에서 w + 1 까지 돌리는 이유는 움직일 수 있는 최대 횟수가 2라면 0, 1, 2가 포함된다.

움직이지 않을 경우도 있기 때문이다.

백준 알고리즘 2240번 자두나무 전체 소스 Github URL

https://github.com/hotehrud/acmicpc/blob/master/algorithm/dp/2240.java

private void solve() {
    int t = sc.nextInt();
    int w = sc.nextInt();
 
    int[][][] dp = new int[3][1001][32];
    int[] arr = new int[1001];
    int ans = 0;
 
    for (int i = 1; i <= t; i++) {
      arr[i] = sc.nextInt();
    }
 
    for (int i = 1; i <= t; i++) {
      for (int j = 1; j <= w + 1; j++) {
        if (arr[i] == 1) {
          dp[1][i][j] = Math.max(dp[1][i - 1][j] + 1, dp[2][i - 1][j - 1] + 1);
          dp[2][i][j] = Math.max(dp[1][i - 1][j - 1], dp[2][i - 1][j]);
        } else {
          if (i == 1 && j == 1) {
            continue;
          }
          dp[1][i][j] = Math.max(dp[2][i - 1][j - 1], dp[1][i - 1][j]);
          dp[2][i][j] = Math.max(dp[1][i - 1][j - 1] + 1, dp[2][i - 1][j] + 1);
        }
      }
    }
    for (int i = 1; i <= w + 1; i++) {
      ans = Math.max(ans, Math.max(dp[1][t][i], dp[2][t][i]));
    }
    System.out.println(ans);
}