백준 그리디 문제풀이 입니다.

문제

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

[나의 풀이]

N = int(input())

distance = list(map(int, input().split()))
n_distance = len(distance)

price = list(map(int, input().split()))
n_price = len(price)

total_distance = sum(distance)
min_price = price[0] * total_distance
import itertools

permu = [i for i in range(total_distance + 1)]
print([permu] * n_distance)

print(permu)
for case in itertools.product(permu, permu, permu):
    flag = True
    prices = 0
    for i in range(n_distance):
        if sum(case[0:i]) < sum(distance[0:i]):
            flag = False
            break
    if flag:
        if sum(case) == total_distance:
            print(case)
            for i in range(n_distance):
                prices += case[i] * price[i]
            print(prices)
            if min_price > prices:
                min_price = prices

print(min_price)

틀린 풀이입니다. 문제 정의 자체는 어렵지 않았지만 주유소별로 주유 리터 경우의 수를 구하는 알고리즘이 복잡해져 해결하는데 어려움이 있었습니다. 그리하여 다른 사람의 코드를 참고하였습니다.🐻🐻🐻

[다른 사람의 풀이]

from sys import stdin

k = int(stdin.readline())
dist = list(map(int, stdin.readline().split()))
cost = list(map(int, stdin.readline().split()))
res = 0

c = cost[0]
for i in range(k - 1):
    if c > cost[i]:
        c = cost[i]
    res += c * dist[i]

print(res)

주유소별 리터당 가격을 확인하면서 현 주유소가 이전 주유소보다 싸다면 현 주유소에서 기름을 구매하는 방식입니다. 주유소별로 몇L씩 구매하는지 경우의 수를 파악하는 저의 풀이와 큰 차이가 있었고 훨씬 간단한 풀이였습니다.🐥🐥🐥

감사합니다.