• 백준 2240번 자두나무 [DP] :: 마이구미
    알고리즘 풀이/동적계획법 2017. 3. 27. 13:28
    반응형

    이번 글은 백준 알고리즘 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가지 경우 중 비교하여 값이 큰 경우를 구하면 된다.

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


    2240번 자두나무


    위 그림처럼 자두를 받을 수 있는 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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    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 == && 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);
    }
    cs


    반응형

    댓글

Designed by Tistory.