• 백준 1535번 안녕 :: 마이구미
    알고리즘 풀이/동적계획법 2017. 8. 26. 14:21
    반응형

    이 글은 백준 알고리즘 문제 1535번 "안녕" 을 풀이에 대해 작성된다.

    백트래킹동적계획법 2가지 풀이를 다뤄볼 것이다.


    세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.

    세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하게 되면 L[i]만큼의 체력을 잃게 되고, J[i]만큼의 기쁨을 얻게 된다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.

    세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이 되거나, 음수가 되면, 죽게되서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.


    문제에서 주의할 점은, 각각의 사람에게 최대 1번만 말할 수 있다는 것이다.

    이 의미는 2번은 말할 수 있다는 것을 알리는 것보다, 1번도 말을 안 할 수도 있다는 것이다.

    즉, 1번부터 3번까지 있다면, 2번에게 인사하지 않고, 1, 3번만 할 수 있다는 것이다.


    그렇기에, 사실 상 할 수 있는 모든 경우를 탐색해야한다.

    처음에는 백트래킹을 활용하여 접근했다.

    6603번 "로또" 문제 풀이를 응용한 구현이기에, 이해가 가지 않는다면 참고하길 바란다.


    1~N번 까지 1번만 인사할 수 있고, 2번만 인사할 수도 있고, 3...4...5....n-1...n번까지 인사할 수도 있다.

    로또 문제는 N번이 고정되어 있던 문제였다고 하면, 이 문제는 1~N번 모두를 탐색하게 된다.

    그 부분의 변수는 shakeN에 해당된다.


    public static void dfs(int life, int happy, int v, int cnt, int shakeN) { if (cnt == shakeN) { if (life > 0) { ans = Math.max(ans, happy); } } else { for (int i = v + 1; i <= n; i++) { if (!visited[i]) { visited[i] = true; dfs(life - hp[i], happy + up[i], i, cnt + 1, shakeN); } } } visited[v] = false; }


    이번에는 동적계획법 풀이를 보자.

    본인의 점화식은 다음과 같다.


    dp[n][hp] = n번까지 인사하고, 남은 체력이 hp일 때의 최대 기쁨


    주어진 예제는 다음과 같이 흘러가게된다.


    3
    1 21 79
    20 30 25


    dp[1][99] = 20

    dp[2][99] = 20

    dp[2][78] = 50

    dp[3][99] = 20

    dp[3][78] = 50

    dp[3][20] = 45


    위 흐름대로 가기 위한 구현은 다음과 같다.


    for (int i = 2; i <= n; i++) { dp[i][100 - hp[i]] = up[i]; for (int j = 100; j > 0; j--) { if (j + hp[i] <= 100 && dp[i - 1][j + hp[i]] != 0) { // max( dp[i - 1][(남은 체력) + (i번째 인사함으로써 소모되는 체력)], dp[i - 1][남은 체력] ) dp[i][j] = Math.max(dp[i - 1][j + hp[i]] + up[i], dp[i - 1][j]); } else { // 무조건 인사하는 것이 아닌, i번째 사람에게 인사를 안할 수도 있는 경우를 위함 dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]); } } }


    이 부분만 이해하면 충분하다. 

    dp[2][78] = dp[1][78 + 21 = 99] + up[2]

    2번째까지 체력이 78일 경우는 (이전 체력이 78일 경우 + 현재 기쁨)을 더해주는 것이다.

    * dp[i - 1][j + hp[i] != 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
    static boolean[] visited;
    static int[] hp = new int[21];
    static int[] up = new int[21];
    static int n, ans;
     
    private void solve() {
        // http://mygumi.tistory.com/203
     
        n = sc.nextInt();
     
        for (int i = 1; i <= n; i++) {
            hp[i] = sc.nextInt();
        }
     
        for (int i = 1; i <= n; i++) {
            up[i] = sc.nextInt();
        }
     
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                visited = new boolean[21];
                dfs(100 - hp[j], up[j], j, 1, i);
            }
        }
        System.out.println(ans);
    }
     
    public static void dfs(int life, int happy, int v, int cnt, int shakeN) {
        if (cnt == shakeN) {
            if (life > 0) {
                ans = Math.max(ans, happy);
            }
        } else {
            for (int i = v + 1; i <= n; i++) {
                if (!visited[i]) {
                    visited[i] = true;
     
                    dfs(life - hp[i], happy + up[i], i, cnt + 1, shakeN);
                }
            }
        }
        visited[v] = false;
    }
    cs


    동적계획법 풀이


    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
    private void solve() {
        n = sc.nextInt();
        int ans = 0;
     
        int[][] dp = new int[21][101];
     
        for (int i = 1; i <= n; i++) {
            hp[i] = sc.nextInt();
        }
     
        for (int i = 1; i <= n; i++) {
            up[i] = sc.nextInt();
        }
     
        dp[1][100 - hp[1]] = up[1];
     
        // dp[i][j] = i번째 사람까지 인사하고 남은 체력이 j일 때 최대 기쁨 
     
        for (int i = 2; i <= n; i++) {
            dp[i][100 - hp[i]] = up[i];
            for (int j = 100; j > 0; j--) {
                if (j + hp[i] <= 100 && dp[i - 1][j + hp[i]] != 0) {
                    // max( dp[i - 1][(남은 체력) + (i번째 인사함으로써 소모되는 체력)], dp[i - 1][남은 체력] ) 
                    dp[i][j] = Math.max(dp[i - 1][j + hp[i]] + up[i], dp[i - 1][j]);
                } else {
                    // 무조건 인사하는 것이 아닌, i번째 사람에게 인사를 안할 수도 있는 경우를 위함 
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                }
            }
        }
     
        for (int i = 100; i > 0; i--) {
            ans = Math.max(dp[n][i], ans);
        }
        System.out.println(ans);
    }
    cs


    반응형

    댓글 0

Designed by Tistory.