백준 9329) 패스트 푸드 상금

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

9329번: 패스트 푸드 상금

문제

ACM-ICPC 아시아 지역 대회기간 중 대전의 패스트 푸드 음식점들은 그들의 음식점을 홍보하기 위해 이벤트를 준비한다. 특정 음식을 먹을 때 마다 스티커를 하나 제공하는데 스티커를 모으면 상금으로 교환할 수 있다. 같은 종류의 스티커가 필요한 상금은 여러 번 교환할 수 있으며, 같은 종류의 스티커를 가진 서로 다른 액수의 상금은 존재하지 않는다. 상금 교환에 필요없는 스티커도 있다.

지역대회를 보러 가면서, 당신의 코치가 패스트 푸드 음식점에서만 식사를 하도록 허락했을 때, 얼마나 많은 상금을 획득할 수 있을까?

입력

입력은 여러개의 테스트 케이스로 이루어져있다. 각 테스트 케이스마다 첫째 줄에는 서로 다른 상금의 종류 n (1 ≤ n ≤ 10) 과 코치가 가지고 있는 스티커의 종류 (1 ≤ m ≤ 30, 종류는 1부터 m까지 번호가 매겨진다) 가 주어진다. 다음 n개의 줄은 상금에 관한 정보가 주어지는데 각 줄마다 첫 번째 정수는 해당 상금에 필요한 스티커의 개수 k (1 ≤ k ≤ m) 가 주어지며 뒤이어 k개의 정수에는 해당 상금에 필요한 스티커의 종류가 주어지며 마지막으로 상금의 액수가 주어진다 (최대 1,000,000) . n개의 모든 입력이 주어진 후 마지막 줄은 코치가 가지고 있는 1부터 m까지 스티커의 개수가 각각 주어진다. 각각의 스티커의 개수는 100개 이하이다.

출력

각각의 케이스마다 최대 상금의 액수를 한줄씩 출력한다.

예제 입력

3
2 10
3 1 2 3 100
4 4 5 6 7 200
2 3 1 4 5 2 2 1 3 4
3 6
2 1 2 100
3 3 4 5 200
1 6 300
1 2 3 4 5 6
3 6
2 1 2 100
3 3 4 5 200
1 6 300
1 2 0 4 5 6

예제 출력

500
2500
1900

 

---

해당 문제를 이해하는 데 시간이 오래 걸렸고, 몇 번이나 틀리는 고배를 마셔야 했다.

 

문제에 나오는 다음의 조건이 바로 핵심이다.

 

 

1)같은 종류의 스티커가 필요한 상금은 여러 번 교환할 수 있으며,
2)같은 종류의 스티커를 가진 서로 다른 액수의 상금은 존재하지 않는다.

1, 2, 3 이라는 스티커에 걸린 상금이 500이라 했을 때,

 

1)번 문항은,

1 : 2개, 2: 2개, 3: 2개가 있으면500 x 2 = 1000 을 획득할 수 있다는 의미이다.

 

2)번 문항은,

1, 2, 3 중에 하나라도 포함한 상금은 존재하지 않는다는 것이다. 즉, 1, 5 라는 다른 종류의 상금은 이미 1, 2, 3 에 포함돼있는 1을 가지고 있으므로 성립하지 않는다.

 

 

 

예제의 첫 번째 테스트 케이스를 이해해보자.

 

2 10
3 1 2 3 100
4 4 5 6 7 200
2 3 1 4 5 2 2 1 3 4

 

코치가 가지고 있는 스티커의 갯수가 1부터 m까지 각각 주어진다는 조건에 의하면,

 

스티커 1 : 2개

스티커 2 : 3개

.....

스티커 10 : 4개

 

 

 

이를 배열로 나타내 본다면 다음과 같다.

현재 총 상금 : 0

 

 

 

 

 

첫 번째 상금 정보 : 1 2 3 은 100을 획득할 수 있으므로 1 2 3 의 원소를 하나씩 제거한다.

현재 총 상금 : 100

 

 

 

 

 

이 때, 3이 0개이므로 더 이상 100은 얻을 수 없다.

두 번째 상금 정보 : 4 5 6 7 은 200을 획득할 수 있으므로 4 5 6 7 의 원소를 하나씩 제거한다.

현재 총 상금 : 300

 

 

 

 

 

4 5 6 7 중에서 0개를 가진 스티커가 없기 때문에 한 번 더 위의 방법을 수행한다.

현재 총 상금 : 500

 

 

 

 

이 때, 6 7 이 0개이므로 더 이상 200은 얻을 수 없다.

그러므로 총 상금은 500이 된다.

 

---

 

위와 같이 문제를 이해하고 코드를 처음 작성했을 때는 다음 로직을 거쳤다. (잘못 작성된 코드)

 

 

1) 상금 정보는 hashmap에 저장. key=상금 value=스티커 종류

2) 최대로 상금을 받아야 하므로 상금이 큰 순서대로 sort (key의 sort)

3) 상금 정보에서 특정 스티커의 갯수가 0이면 셀 필요가 없으므로 재낌

4) 만약 0개가 아니라면 스티커 갯수가 담긴 배열에 하나씩 차감

5) 결과값에 상금을 더해줌

 

 

위의 알고리즘대로 작성한 코드는 다음과 같다.

 

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    repeat(readLine().toInt()) {
        val (n, m) = readLine().split(" ").map { it.toInt() }
        val info = hashMapOf<Int, List<Int>>()
        repeat(n) {
            val s = readLine().split(" ").map { it.toInt() }
            info[s.last()] = s.subList(1, s[0] + 1)
        }

        val coach = readLine().split(" ").map { it.toInt() }.toIntArray()
        var result = 0

        info.entries.sortedByDescending { it.key }.forEach {
            var isCheck = false
            while (true) {
                for(item in it.value) {
                    if (coach[item - 1] <= 0) {
                        isCheck = true
                        break
                    }
                }
                if(isCheck) break
                else {
                    it.value.forEach { i -> coach[i-1]-- }
                    result += it.key
                }
            }
        }
        bw.write("$result\n")
    }
    bw.flush()
    bw.close()
}

 

하지만,,,,,

한 가지 간과한 것이 존재했다. 빠르게 상금 정보를 얻기 위해 hashMap을 통해 저장했지만,

상금이 겹칠 수도 있기 때문에 이는 옳은 구현이 아니였다.

 

 

많은 고민 끝에 다음과 같은 로직으로 재탄생시켰다. (성공한 코드)

 

 

1) 상금 정보의 스티커는 arrayList 안에 list 형태로 저장. 상금은 price라는 배열을 따로 생성해서 저장

• e.g. arrayList[0] = {1, 2, 3}. price[0] = 100

2) 특정 스티커의 갯수에다가 1을 뺐다고 가정할 때 0보다 작은지 판별하는 함수 작성.

만약 모두가 0보다 크다면 true, 하나라도 0보다 작다면 false

 

3) true라면 특정 스티커의 갯수를 실제로 1씩 뺀다. 그리고 결과값에 상금을 추가.

 

 

위의 알고리즘대로 구현한 코드는 다음과 같다.

 

import kotlin.collections.ArrayList

lateinit var coupon : ArrayList<List<Int>>
lateinit var coach : IntArray
lateinit var price : IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    repeat(readLine().toInt()) {
        val (n, m) = readLine().split(" ").map { it.toInt() }

        coupon = ArrayList()
        price = IntArray(n)
        repeat(n) {
            val s = readLine().split(" ").map { it.toInt() }
            coupon.add(s.subList(1, s[0] + 1))
            price[it] = s.last()
        }

        coach = readLine().split(" ").map { it.toInt() }.toIntArray()
        var result = 0

        for (i in 0 until n) {
            while (isPos(i)) {
                for(item in coupon[i]) {
                    coach[item-1]--
                }
                result+= price[i]
            }
        }
        bw.write("$result\n")
    }
    bw.flush()
    bw.close()
}

private fun isPos(i: Int): Boolean {
    for(item in coupon[i]) {
        val data = coach[item-1] -1
        if(data < 0)
            return false
    }
    return true
}

 

 

해당 문제를 통해서 while문 안의 조건으로 함수를 처음 써봤다.

이를 계기로 구현에 능숙하기까지 개미 한 마리의 머리 길이 만큼 다가설 수 있었다.

 

꾸준하게, 그리고 깊이 있게 공부해서 내 것으로 만들자!