백준 1535번 안녕 :: 마이구미

이 글은 백준 알고리즘 문제 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 조건은 흐름을 보다 잘 보여주기 위함이기에, 생략해도 된다.

* 로그를 찍어보면서 확인하면 이해가 빠를 것이라 생각한다.

백트래킹 풀이

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;
}

동적계획법 풀이

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);
}