백준 4781) 사탕 가게 [부제 : 배낭문제]

https://www.acmicpc.net/problem/4781

4781번: 사탕 가게

 

문제

상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 누가 더 건강이 안 좋아질 수 있는지 내기를 하자고 했다. 상근이는 내기를 그 즉시 받아들였다.

두 사람은 같은 돈을 가지고 가게에 들어가서 사탕을 산다. 이때, 구매한 사탕의 칼로리가 더 큰 사람이 내기에서 이기게 된다.

상근이는 잠시 화장실에 갔다온다고 핑계를 댄 뒤에, 노트북을 열고 사탕 가게의 시스템을 해킹하기 시작했다. 이 시스템에는 현재 사탕 가게에 있는 사탕의 가격과 칼로리가 모두 등재되어 있다. 각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다. 또, 사탕은 쪼갤 수 없기 때문에, 일부만 구매할 수 없다.

사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하시오.

입력

각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다.

다음 n개 줄에는 각 사탕의 칼로리 c와 가격 p가 주어진다. (1 ≤ c ≤ 5,000, 0.01 ≤ p ≤ 100.00) c는 항상 정수, p는 항상 소수점 둘째자리이다.

입력의 마지막 줄에는 '0 0.00'이 주어진다.

출력

각 테스트 케이스에 대해서, 상근이가 돈 m을 가지고 구매할 수 있는 가장 높은 칼로리를 출력한다.

 

 

---

 

접근 방법

 

이 문제는 배낭 문제에서 파생된 문제라고 봐도 무방하다.

배낭 문제로 비유하자면,

 

물건(사탕)이 n개 있을 때, 배낭의 무게 제한(상근이가 가진 돈)이 있고, 최대 가치(최대 칼로리)가 되도록 물건을 배낭에 담는다.

 

하지만 배낭 문제를 좀 더 응용한 문제인데,

배낭 문제는 물건을 한 번 담으면 끝이므로,이전에 담은 물건에서 현재 물건을 담을 수 있는지를 판별하고,

해당 문제는 사탕을 여러 번 담을 수 있으므로, 현재 물건을 더 많이 담을 때 가치가 이전보다 높을 수 있음을 고려해야 한다.

이를 점화식으로 차이점을 본다면 확연히 드러난다.

 

 #2차원 배열

#배낭 문제 점화식
D[i][j] = maxOf(D[i-1][j], D[i-1][j-무게] + 가치)  (if, j-무게 >= 0)

#사탕 가게 문제 점화식
D[i][j] = maxOf(D[i-1][j], D[i][j-가격] + 칼로리)  (if, j-가격 >= 0)

 

 

해당 문제는 가격을 소수형으로 값을 입력받고 있다.

배열에 접근할 때는 정수형만 가능하기에 소수 -> 정수로 바꾼다.

0.01 ~ 100.0 이라는 범위를 가지고 있으니 X100을 해준다면 1 ~ 100 까지의 정수형 범위를 만들 수 있다.

 

하지만,,,,,

막연히 X100만 해준다면 채점 결과가 100%에서 틀렸습니다. 라는 문구를 마주하게 될 것이다.

double형은 부동 소수점이기에 100을 곱한다해서 정수가 나온다는 보장이 없기 때문이다.

 

 

0.01에서 0.1의 범위가 있을 때-

 

Case1. 100만 곱할 경우

 

 

    var t = 0.01
    while(t < 1) {
        println((t * 100))
        t += 0.01
    }

 

0.1 * 100 =  10

0.11 * 100 = 10.99999 (11이 출력되기를 기대)

 

뿐만 아니라 t * 100 를 Int형으로 변환해도 값은 변함이 없다.

 

 

 

Case2. X100 + 0.5 할 경우

 

이를 해결하기 위해선 0.5 를 더해준다음 Integer형으로 바꿔 소수점 이하의 자리를 버린다면 원하는 결과를 얻게 된다.

 

 

    var t = 0.01
    while(t < 1) {
        println((t * 100).toInt())
        t += 0.01
    }

 

 

 

첫 번째 풀이

 

 

위의 접근 방법대로 풀이를 진행하니

 

1. 2차원 배열을 이용한 점

2. 가격과 칼로리 배열을 초기화하고 입력받은 점

 

이러한 이유로 시간이 많이 걸릴 수 밖에 없었다.

 

fun main() = with(System.`in`.bufferedReader()) {
    val ans = StringBuilder()
    while (true) {
        val input = readLine().split(" ")
        if(input[0] == "0" && input[1] == "0.00")
            break

        val n = input[0].toInt()
        val m = (input[1].toDouble() * 100 + 0.5).toInt()

        val dp = Array(n+1) {IntArray(m+1)}
        val c = IntArray(n+1)
        val p = IntArray(n+1)

        for(i in 1..n) {
            val s = readLine().split(" ")
            c[i] = s[0].toInt()
            p[i] = (s[1].toDouble() * 100 + 0.5).toInt()
        }

        for(i in 1..n) {
            for(j in 1..m) {
                dp[i][j] = dp[i-1][j]
                if(j - p[i] >= 0) {
                    dp[i][j] = maxOf(dp[i][j], dp[i][j-p[i]] + c[i])
                }
            }
        }
        ans.appendLine(dp[n][m])
    }
    println(ans)
}

 

 

두 번째 풀이

 

 

dp 배열을 1차원으로 초기화해서 푸니 확실히 공간도 현저히 줄었을 뿐만 아니라 시간 또한 1000ms 정도 줄일 수 있었다.

 

1차원으로 풀 때 주의할 점이 있다!

사탕을 1 ~ n개에 대해 1 ~ m 까지 최대 칼로리를 찾게 되면 이미 dp 배열에 메모한 값이 중복되거나 변경될 수 있다.

그렇기 때문에 1 ~ m 까지 최대 칼로리를 찾되 1 ~ n 까지 차례대로 사탕의 가격을 고려하는 것이다.

즉, 1의 가격부터 시작해서 1 ~ n 개의 사탕을 살 수 있는지 확인한다. (다 찾고 나서 다음으로 2의 가격부터)

이렇게 되면 중복 문제를 해결 할 수 있다.

 

참고로 이 개념과 비슷한 문제는 다음 문제와 같다.

 

https://www.acmicpc.net/problem/15989  

15989번: 1, 2, 3 더하기 4

 

 

fun main() = with(System.`in`.bufferedReader()) {
    val ans = StringBuilder()
    while (true) {
        val input = readLine().split(" ")
        if(input[0] == "0" && input[1] == "0.00")
            break

        val n = input[0].toInt()
        val m = (input[1].toDouble() * 100 + 0.5).toInt()

        val dp = IntArray(m+1)
        val c = IntArray(n+1)
        val p = IntArray(n+1)

        for(i in 1..n) {
            val s = readLine().split(" ")
            c[i] = s[0].toInt()
            p[i] = (s[1].toDouble() * 100 + 0.5).toInt()
        }

        for(j in 1..m) {
            for(i in 1..n) {
                if(j >= p[i]) {
                    dp[j] = maxOf(dp[j], dp[j-p[i]] + c[i])
                }
            }
        }
        ans.appendLine(dp[m])
    }
    println(ans)
}

 

 

마지막 풀이

 

 

두 번째 풀이에서 불필요한 요소를 싹 다 제거했더니 놀랍도록 속도가 많이 개선됐다!

 

가격과 칼로리 배열을 따로 초기화하지 않고,

어차피 차례대로 입력받게 되니 반복문 안에서 입력받는 동시에, 내부에 for문으로 dp 연산을 진행했다.

뿐만 아니라 j >= p 이어야만 dp[j-p]를 계산할 수 있으므로 p ~ m 까지 범위를 설정함으로써 연산의 수를 줄였다.

 

fun main() = with(System.`in`.bufferedReader()) {
    val ans = StringBuilder()
    while (true) {
        var input = readLine().split(" ")
        val n = input[0].toInt()
        val m = (input[1].toDouble() * 100 + 0.5).toInt()

        if (n == 0 && m == 0) break

        val dp = IntArray(m + 1)

        repeat(n) {
            input = readLine().split(" ")
            val s = input[0].toInt()
            val p = (input[1].toDouble() * 100 + 0.5).toInt()

            for (j in p..m) {
                if (j >= p) dp[j] = maxOf(dp[j], dp[j - p] + s)
            }
        }
        ans.appendLine(dp[m])
    }
    println(ans)
}