Orchemi

Orchemi

I start where others stop.

[BOJ][⚪1][백준#24954] 물약 구매

작성:    

업데이트:

카테고리:

태그: , , ,

문제 출처

BAEKJOON Online Judge #24954


문제

준겸이는 모험가이다. 모험을 떠나기 위해서는 철저한 사전 준비를 갖추어야 한다. 준겸이는 모험을 떠나기 전 $N$종류의 물약을 모두 구매하려고 한다. 물약 상점에 들른 준겸이는 각 물약이 $1$번부터 $N$번까지 번호가 매겨져 있다는 것을 알아냈다. 그런데, 물약 상점에서는 오늘 특별한 이벤트를 하고 있었다. 특정 물약을 구매하면, 어떤 다른 물약들을 할인해준다는 것이었다. 원래 $i$번째 물약의 가격은 동전 $c_i$개이다. 만약 $i$번째 물약을 구매하면, $p_i$종류의 다른 물약의 가격이 내려간다. 할인은 중첩된다. 예를 들어 $1$번 물약을 구매하면 $3$번 물약의 가격이 동전 $1$개만큼 할인되고, $2$번 물약을 구매하면 역시 $3$번 물약의 가격이 동전 $2$개만큼 할인된다고 하자. 그러면 두 물약을 모두 구매하고 나서 $3$번 물약을 구매할 때 동전 $3$개만큼의 할인을 받을 수 있다. 단, 물약의 가격이 내려가더라도 $0$ 이하로 내려가지는 않는다. 예를 들어, 원래 가격이 동전 $5$개인 물약이 동전 $4$개를 넘는 만큼 할인되더라도 가격은 동전 $1$개가 된다.  준겸이는 신나서 물약을 구매하려다가, 물약을 구매하는 순서가 중요하다는 사실을 깨달았다. 준겸이를 위해 물약을 가장 싸게 샀을 때 그 비용을 알려주자.


입력

첫째 줄에 물약의 종류 $N$이 주어진다. 둘째 줄에 물약의 가격 $c_i$가 공백을 사이에 두고 주어진다($1 \le i \le N$).  다음 줄부터, 물약 할인 정보가 $N$개 주어진다. $i$번째로 주어지는 물약 할인 정보는 다음과 같다($1 \le i \le N$).  $p_i$가 주어진다. 다음 $p_i$개의 줄에, 물약 번호 $a_j$와 할인되는 가격 $d_j$가 주어진다. 이는 $i$번 물약을 구매하고 나면 물약 $a_j$가 동전 $d_j$개만큼 할인된다는 뜻이다.


출력

첫째 줄에 물약을 가장 싸게 샀을 때 동전이 몇 개 필요한지 출력한다. 


제한

$2 \le N \le 10$ $1 \le c_i \le 1\,000$ $0 \le p_i \le N-1$ 각 $i$에 대해, 모든 $a_j$는 서로 다르고 $a_j \neq i$ $1 \le d_j \le 1\,000$


예제

입력

4
10 15 20 25
2
3 10
2 20
0
1
4 10
1
1 10


출력

36


My Sol

import sys
input = sys.stdin.readline

def dfs(i):
    global nzeros

    if i == nzl:
        check()
        return

    for k in range(i, nzl):
        nzeros[i], nzeros[k] = nzeros[k], nzeros[i]
        dfs(i+1)
        nzeros[i], nzeros[k] = nzeros[k], nzeros[i]


def check():
    global minCost
    costs = potions[::]
    nowCost = 0

    i = 0
    while i < nzl:
        buy = nzeros[i]
        nowCost += costs[buy]
        for fi, fc in dcs[buy]:
            costs[fi] = costs[fi]-fc if costs[fi]-fc > 0 else 1
        i += 1

    for i in zeros:
        nowCost += costs[i]

    minCost = min(minCost, nowCost)


pl = int(input())
potions = [0] + list(map(int, input().split()))
dcs = [[] for _ in range(pl+1)]

nzl = 0
zeros = []
nzeros = []

for i in range(1, pl+1):
    dl = int(input())
    if not dl:
        zeros.append(i)
        continue

    nzl += 1
    nzeros.append(i)
    for _ in range(dl):
        fi, fc = map(int, input().split())
        dcs[i].append((fi, fc))

minCost = 0xffffff
dfs(0)
print(minCost)

N이 10개이지만, 모든 가능한 경우의 수를 고려한다면 경우의 수가 상당히 많아져 연산시간이 폭발적으로 늘어날 수 있다. 때문에 가지치기 조건을 고민해보았다. 내 풀이의 핵심은 할인 정보가 없는 포션이다. 이 포션들은 다른 포션들을 할인시켜주지 않으므로 먼저 살 이유가 없다.

때문에 할인정보를 입력 받는 과정에서부터 엮여있는 할인 정보가 있는지 없는지 여부를 판단하여 그룹을 나누었다. 그리고 할인정보가 있는 그룹들(nzeros)만 dfs를 이용해 순서를 달리하는 모든 경우의 수를 구해주었고, check 함수에서는 nzeros에 배치된 순서대로 물약을 구매하며 다른 물약들의 가격을 깎아 나갔다. 물론 이 과정에서 조건처럼 0 이하가 된다면 1로 유지시켜주는 조건문을 잊지 않는다.

이후 nzeros의 모든 물약들을 구매했다면, 가능한 할인은 모두 실시하였으므로, zeros에 있는 물약 번호들의 물약을 모두 구매하여 minCost와 비교하면 된다. 즉, 핵심은 물약 결합 할인이 없는 물약들은 맨 나중에 구매하는 것이고, 이를 통해 가능한 경우의 수의 크기를 줄여주는 것이다.


결과

맞았습니다!!

492ms의 연산시간으로 상당히 빠른 연산시간으로 문제를 마쳤다.

[TMI] 원티드 코딩테스트 쇼미더코드에서 1번 문제로 나왔던 문제이다. 문제가 너무 어렵게 생겨서 코딩테스트 때는 넘겼었는데 실버1 난이도로 나와서 당황했다. 하지만 2번 문제였던 골드 난이도 문제보다도 까다로웠던만큼 만만한 문제는 아니었다. 우선 문제 설명부터가 더러워서…


모범답안

출처

import sys

input = sys.stdin.readline
n = int(input())
price = list(map(int, input().split()))

graph = [[] for _ in range(n)]

for i in range(n):
    p = int(input())
    for _ in range(p):
        a, cost = map(int, input().split())
        graph[i].append([a - 1, cost])

dp = [float('inf')] * (1 << n)


def solve(current):
    for i in range(n):
        if (1 << i & current):
            continue
        next_bit = current | (1 << i)
        total_price = dp[current] + price[i]
        if total_price < dp[next_bit]:
            dp[next_bit] = total_price
            diff = []
            for discount, discount_amount in graph[i]:
                next_price = max(price[discount] - discount_amount, 1)
                diff.append([discount, price[discount]])
                price[discount] = next_price
            solve(next_bit)
            for discount, discount_amount in diff:
                price[discount] = discount_amount


for i in range(n):
    dp[1 << i] = price[i]
    diff = []
    for discount, discount_amount in graph[i]:
        next_price = max(price[discount] - discount_amount, 1)
        diff.append([discount, price[discount]])
        price[discount] = next_price
    solve(1 << i)
    for discount, discount_amount in diff:
        price[discount] = discount_amount

print(dp[-1])

내 풀이시간의 절반도 안 되는 212ms의 연산시간의 풀이가 있어 분석해보려 한다. 일단 눈에 띄는 것은 DP를 사용하셨다. 나도 고려했지만 점화식을 찾을 엄두가 나지 않아 포기한 DP 방식…

그런데 특이한 점은 1차원 배열의 dp를 사용하였고, 물약의 개수 n을 bit shift로 ({2}^{n})개 만큼 만들어주었다는 것이다. 그리고…. 이외에는 비트마스킹을 사용하셨는데 도저히 이해가 안된다ㅋㅋㅋㅋ 분석은 더 성장한 나에게 맡긴다.

당연하면서도 센스 있었던 것은 next_price = max(price[discount] - discount_amount, 1) 부분인데, 알고리즘 때 max 함수를 금지하니까 습관이 돼서 나는 costs[fi] = costs[fi]-fc if costs[fi]-fc > 0 else 1 이렇게 하는데 저런 방식이 더 가독성도 좋고 편하게 표시할 수 있는 것 같다. 배워봐야겠다.

댓글남기기

참고