• 백준 14720번 우유 축제 :: 마이구미
    알고리즘 풀이/동적계획법 2017. 9. 25. 20:13
    반응형

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

    본인은 동적계획법을 통해 문제를 해결했다.

    최근 충남대에서 열린 "생각하는 프로그래밍 대회" 에 출제되었다.

    14720번 - https://www.acmicpc.net/problem/14720


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

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

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

    영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 우유 거리에는 우유 가게들이 일렬로 늘어서 있다.

    영학이는 우유 거리의 시작부터 끝까지 걸으면서 우유를 사먹고자 한다.

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

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

    우유거리에는 사람이 많기 때문에 한 번 지나친 우유 가게에는 다시 갈 수 없다.

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


    문제에 대한 점화식은 다음과 같다.


    dp[n][milk] = n번째 가게까지 어떤 우유를 마셨을 때 우유의 최대 개수


    dp[n][0] = (dp[n-1][2] + 1 or dp[n-1][0])

    => 딸기우유 = 이전 가게까지 바나나우유를 마셨을 때의 최대 개수


    dp[n][1] = (dp[n-1][0] + 1 or dp[n-1][1])

    => 초코우유 = 이전 가게까지 딸기우유를 마셨을 때의 최대 개수


    dp[n][2] = (dp[n-1][1] + 1 or dp[n-1][2])

    => 바나나우유 = 이전 가게까지 초코우유를 마셨을 때의 최대 개수


    for (int i = start + 1; i < n; i++) { int milk = array[i]; dp[i][0] = milk == 0 ? dp[i - 1][2] + 1 : dp[i - 1][0]; dp[i][1] = milk == 1 && dp[i][2] < dp[i][0] ? dp[i - 1][0] + 1 : dp[i - 1][1]; dp[i][2] = milk == 2 && dp[i][0] < dp[i][1] ? dp[i - 1][1] + 1 : dp[i - 1][2]; }


    딸기우유를 먹지 않은 상태에서 초코 우유를 마실 수 있는 경우.

    초코우유를 먹지 않은 상태에서 바나나우유를 마실 수도 있는 경우.

    문제의 규칙대로 적용하기 위해 위와 같은 조건이 필요하다.


    심화된 문제로 14722번 "우유 도시" 문제가 존재한다.

    관련 글 - http://mygumi.tistory.com/224



    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    private void solve() {
        int n = sc.nextInt();
        int[] array = new int[n];
        int[][] dp = new int[n][3];
     
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
     
        if (array[0== 0) {
            dp[0][0= 1;
        }
     
        for (int i = 1; i < n; i++) {
            int milk = array[i];
     
            dp[i][0= milk == ? dp[i - 1][2+ : dp[i - 1][0];
            dp[i][1= milk == && dp[i][2< dp[i][0] ? dp[i - 1][0+ : dp[i - 1][1];
            dp[i][2= milk == && dp[i][0< dp[i][1] ? dp[i - 1][1+ : dp[i - 1][2];
        }
        System.out.println(Math.max(dp[n - 1][0], Math.max(dp[n - 1][1], dp[n - 1][2])));
    }
    cs


    반응형

    댓글 0

Designed by Tistory.