[백준 2024/02/23] 13305번 주유소

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

13305번: 주유소

 

1. 접근 방법

값이 싼 주유소에 대해서 오름차순 정리를 한 후, 

처음에는 값이 싼 주유소에 대해서 뒤에 있는 거리들까지 기름을 채우고 이동하는 식으로 식을 구성했었다.

하지만, 시간초과가 났었다.

시간 초과가 난 코드는 아래와 같다.

len_city = int(input())
d = list(map(int, input().split()))
city = list(map(int, input().split()))

city_w_index = [[money, city_num] for city_num, money in enumerate(city)]
#print(city_w_index)
city_w_index.sort()
#print(city_w_index)

visited = [False]*(len_city+1)
total = 0

for m, c in city_w_index:
    if all(visited):
        break
    if visited[c]:
        continue
    for i in range (c+1, len(city), 1):
        if not visited[i]:
            total += d[i-1] * m
            visited[i] = True

 

그래서 방식을 바꾸었다.

순서대로 장소를 방문한 후, 방문한 곳의 기름값을 visited_city라는 리스트에 정리해 두었다.

이후, 새로운 장소에 방문할 때마다 현재까지 저장된 기름값들 중 최솟값을 찾고, 해당 최솟값에 대해서 다음 거리를 곱해주었다.

 

아래 예제를 통해서 더 깊게 이야기해 볼 것이다. 

[2, 3, 1] # distance를 저장한 리스트
[5, 2, 4, 1] # 해당 위치의 기름값을 저장한 곳

 

이런식으로 저장하였다.

5 -> 2 -> 4 -> 1로 방문을 하였다.

우선 visited_city.append(5) 를 해주었다.

 

이후 min(visited_city) 를 통해 5를 찾아주었다. 2*5를 해서 total이라는 곳에 더해주었다.

 

이후 다음으로 2에 방문해서, visited_city.append(2) 를 해주었다.

min(visited_city) 를 통해서 2를 찾아주었고, 2*3 을 total에 더해주었다.

 

이런식으로 접근하였다. 

 

2. 코드

def min_total_cost(len_city, city,d):
    visited_city = []
    total = 0
    for i in range(0, len_city-1, 1):
        visited_city.append(city[i])
        total += d[i] * min(visited_city)

    return total


def main():
    len_city = int(input())
    d = list(map(int, input().split()))
    city = list(map(int, input().split()))
    print(min_total_cost(len_city, city, d))


if __name__ == '__main__':
    main()