[Python] 18186번: 라면 사기 (Large)

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

18186번: 라면 사기 (Large)

 

아이디어

1. 블럭 하나를 여러 블럭으로 나누어 돈을 절약할 수 있다.

B, C 값에 따라서 1, 2, 3번 구매 옵션의 비용이 달라진다. 경우에 따라 (블럭 3 비용) > (블럭 1 비용) + (블럭 2 비용)이 성립하는 등의 케이스가 발생할 수 있다. 극단적으로, B = 1, C = 100인 경우 블럭 1은 1원, 블럭 2는 101원이 들기 때문에 블럭 1로 나누어 구매하는 것이 옳은 방법이다.

이러한 경우들을 정리하면 다음과 같다:

- (블럭 3 비용) > (블럭 1 비용) + (블럭 2 비용)

- (블럭 3 비용) > (블럭 1 비용) * 3

- (블럭 2 비용) > (블럭 1 비용) * 2

2. 블럭 여러 개에 대해

위과 같은 블럭이 있다고 해보자. 아래와 같이 두 방법으로 블럭을 소비할 수 있다:

이러한 케이스들을 모두 고려해보면 다음 두 개의 경우로 결론이 난다:

1. 2 + 3 vs 3 + 1 + 1

 

2. 2 + 2 vs 3 + 1

 

소스 코드

import sys
input = sys.stdin.readline

def buy(index, seq, count = 1):
    global cost

    for i in range(seq):
        nums[index + i] -= count
    
    to_spend = costs[seq - 1]
    if seq == 3:
        if costs[0] * 3 < costs[2]: to_spend = costs[0] * 3
        elif costs[1] + costs[0] < costs[2]: to_spend = costs[1] + costs[0]
    elif seq == 2 and costs[0] * 2 < costs[1]:
        to_spend = costs[0] * 2
    cost += to_spend * count

def solution():
    global cost

    #  @       @@@
    # @@@@ vs @@
    flag_23 = costs[2] + costs[0] * 2 > costs[1] + costs[2]

    # @@@ @ vs @@ @@
    flag_22 = costs[2] + costs[0] > costs[1] * 2

    cost = 0
    i = 0
    while i < N:
        if nums[i] == 0:
            i += 1
        else:
            min2 = min(nums[i:i + 2]) if i + 1 < N else False
            min3 = min(min2, nums[i + 2]) if i + 2 < N else False
            min4 = min(min3, nums[i + 3]) if i + 3 < N else False

            if flag_23 and i + 3 < N and nums[i + 1] > nums[i + 2] and nums[i + 3] >= 1:
                minn = min(nums[i], nums[i + 1], nums[i + 1] - nums[i + 2])
                buy(i, 2, 1 if minn <= 2 else minn - 2)
            elif flag_22 and i + 3 < N and min4 >= 1:
                buy(i, 2, 1 if min4 <= 2 else min4 - 2)
            
            elif i + 2 < N and min3 >= 1:
                buy(i, 3, 1 if min3 <= 2 else min3 - 2)
            elif i + 1 < N and min2 >= 1:
                buy(i, 2, 1 if min2 <= 2 else min2 - 2)
            else:
                buy(i, 1, 1 if nums[i] <= 2 else nums[i] - 2)
        
    return cost

N, B, C = map(int,input().split())
costs = [B, B + C, B + C * 2]
nums = list(map(int,input().split()))
print(solution())

 

+ 테스트 코드

아래 테스트 코드는 문제를 풀 때 직접적으로 활용한 테스트 코드로, 백트래킹을 이용한 DFS로 모든 경우를 고려하는 dfs() 함수를 작성하였다.(당연히 시간이 오래 걸린다.) 필자는 해당 코드를 통해 이 문제를 테스트 주도로 해결하였다.

import sys
import random
input = sys.stdin.readline

def solution():
    # TODO: Paste your solution function returning a minimum cost
    return 0

def dfs(index, nums, cost):
    if index >= N:
        return cost
    if nums[index] == 0:
        return dfs(index + 1, nums, cost)
    
    result = float('inf')
    if index + 2 < N and min(nums[index], nums[index + 1], nums[index + 2] >= 1):
        nums[index] -= 1
        nums[index + 1] -= 1
        nums[index + 2] -= 1
        result = min(result, dfs(index, nums, cost + costs[2]))
        nums[index] += 1
        nums[index + 1] += 1
        nums[index + 2] += 1
    
    if index + 1 < N and min(nums[index], nums[index + 1] >= 1):
        nums[index] -= 1
        nums[index + 1] -= 1
        result = min(result, dfs(index, nums, cost + costs[1]))
        nums[index] += 1
        nums[index + 1] += 1
    
    if nums[index] >= 1:
        nums[index] -= 1
        result = min(result, dfs(index, nums, cost + costs[0]))
        nums[index] += 1
    
    return result

for t in range(10000):
    N = random.randrange(1, 10)
    B = random.randrange(1, 10)
    C = random.randrange(1, 10)
    costs = [B, B + C, B + C * 2]
    nums = []
    for i in range(N):
        nums.append(random.randrange(0, 5))
    print("========case {0}========".format(t))
    print("N = {0}, B = {1}, C = {2}, costs = {3}".format(N, B, C, costs))
    print(' '.join(map(str, nums)))
    
    answer, my_solution = dfs(0, nums, 0), solution()
    if (answer != my_solution):
        print("Failed: answer = {0}, my solution = {1}".format(answer, my_solution))
        break