• 백준 14722번 우유 도시 :: 마이구미
    알고리즘 풀이/동적계획법 2017. 9. 26. 11:24
    반응형

    이 글은 백준 알고리즘 문제 14722번 "우유 도시" 를 풀이한다.

    14720번 "우유 축제" 에서 조금 더 심화된 문제라고 볼 수 있다.

    그렇기에, 동적계획법을 통해 문제를 해결한다.

    14722번 문제 - https://www.acmicpc.net/problem/14722

    14720번 풀이 - http://mygumi.tistory.com/223


    영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.

    입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 

    1. 맨 처음에는 딸기우유를 한 팩 마신다.
    2. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
    3. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
    4. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 

    저번 축제에서 수많은 우유를 마셨지만 더욱 우유에 갈증을 느낀 영학이는 우유 여행을 떠났다.

    맛있는 우유를 찾아 떠난 영학이는 수많은 우유 가게로 둘러 쌓인 어느 도시에 도착했다.

    이 도시는 정사각형 형태의 2차원 격자 모양으로 남북으로 N개, 동서로 N개, 총 N*N개의 우유 가게들이 있다.

    영학이는 도시의 서북쪽 끝 (1, 1)에서 출발해서 동남쪽 아래 (N, N)까지 까지 가면서 우유를 사 마신다. 

    각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.

    각각의 우유 가게 앞에서, 영학이는 우유를 사 마시거나, 사 마시지 않는다.

    So cooooool~한 영학이는 오직 동쪽 또는 남쪽으로만 움직이기 때문에 한 번 지나친 우유 가게에는 다시 가지 않는다.

    영학이가 마실 수 있는 우유의 최대 개수를 구하여라.


    우유 축제와 다른 점은 움직이는 경로가 1차원 배열에서 2차원 배열로 변했다.

    즉, 단순히 오른쪽으로만 이동했다면, 이번 문제는 오른쪽과 아래쪽으로 이동할 수 있다.


    기존의 점화식이였던 2차원 배열에서 3차원 배열로 전환하면 된다.

    이전 점화식을 이해했다면, 충분히 이해하리라 생각한다.


    dp[m][n][milk] = 좌표 (m,n) 가게까지 어떤 우유를 마셨을 때 우유의 최대 개수


    코드를 보면 편의를 위해 0행과 0열을 미리 셋팅했다는 걸 참고바란다.


    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
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    private void solve() {
        int n = sc.nextInt();
        int[][] array = new int[n][n];
        int[][][] dp = new int[n][n][3];
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                array[i][j] = sc.nextInt();
            }
        }
     
        if (array[0][0== 0) {
            dp[0][0][0= 1;
        }
     
        // ----------------------초기 셋팅-----------------------------------
        for (int i = 1; i < n; i++) {
            int milk = array[0][i];
     
            dp[0][i][0= milk == ? dp[0][i - 1][2+ : dp[0][i - 1][0];
            dp[0][i][1= milk == && dp[0][i][2< dp[0][i][0] ? dp[0][i - 1][0+ : dp[0][i - 1][1];
            dp[0][i][2= milk == && dp[0][i][0< dp[0][i][1] ? dp[0][i - 1][1+ : dp[0][i - 1][2];
        }
     
        for (int i = 1; i < n; i++) {
            int milk = array[i][0];
     
            dp[i][0][0= milk == ? dp[i - 1][0][2+ : dp[i - 1][0][0];
            dp[i][0][1= milk == && dp[i][0][2< dp[i][0][0] ? dp[i - 1][0][0+ : dp[i - 1][0][1];
            dp[i][0][2= milk == && dp[i][0][0< dp[i][0][1] ? dp[i - 1][0][1+ : dp[i - 1][0][2];
        }
        // ---------------------------------------------------------------
     
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                int milk = array[i][j];
     
                dp[i][j][0= milk == 
                    ? Math.max(dp[i][j - 1][2+ 1, dp[i - 1][j][2+ 1)
                    : Math.max(dp[i][j - 1][0], dp[i - 1][j][0]);
                dp[i][j][1= milk == && dp[i][j][2< dp[i][j][0]
                    ? Math.max(dp[i][j - 1][0+ 1, dp[i - 1][j][0+ 1)
                    : Math.max(dp[i][j - 1][1], dp[i - 1][j][1]);
     
                dp[i][j][2= milk == && dp[i][j][0< dp[i][j][1]
                    ? Math.max(dp[i][j - 1][1+ 1, dp[i - 1][j][1+ 1)
                    : Math.max(dp[i][j - 1][2], dp[i - 1][j][2]);
            }
        }
        System.out.println(Math.max(dp[n - 1][n - 1][0], Math.max(dp[n - 1][n - 1][1], dp[n - 1][n - 1][2])));
    }
    cs


    반응형

    댓글 0

Designed by Tistory.