백준 13305번 주유소 파이썬 풀이

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

13305번: 주유소

이동하는데 총 필요한 예산의 최소 값을 구하는 문제인데 나중에 다시 풀어볼만 해보여서 남겨봅니다.

특히 조건이 더하면서 따라 유형과 난이도를 바꾸기 좋은 문제인것 같습니다.

예를 들어 한 도시에서 가는 길이 여러개라던가 아니면 연료통의 크기에 제한을 걸어둔다던가하면 좀 어려워질듯합니다.

 

우선 가장 먼저 생각나는 것은 연료통 사이즈에 제한이 없기 때문에 가장 저렴한 도시에 가서 가득 채우면 되겠구나였습니다.

당연한 얘기지만 그러기 위해서는 우선 가장 저렴한 도시에 가야합니다.

예를 들어 a,b,c,d,e 순으로 도시가 주어지고 c가 가장 저렴하다고 했을때 c에 도달을 해야한다면 c이후의 도시는 다 건너뛰고 c에서 가득 채워가면 되므로 c 이후는 고려할 필요가 없습니다. 그렇다면 문제는 시작지점과 종료지점이 a에서 c까지로 바뀌게 됩니다.

그럼 또 다시 a와 c에서 가장 저렴한 도시를 찾는 문제로 바뀌는데요. 이런 식으로 문제가 구간별로 세분화 되어집니다. 

 

하지만 그렇다고 계속 min 함수를 쓰기에는 시간복잡도에서 리스크가 있어 보입니다.

시간제한이 2초이고 도시의 개수 n은 100,000 이므로 최대 O(nlogn)에서 마무리 해야됩니다. (1초에 연산량 1억)

 

간단히 말하면 한 도시에서는 지금보다는 가격이 낮은 도시까지 갈만큼의 연료만 넣어주면 됩니다.

 

두가지로 풀었는데 하나는 O(n)짜리이고 하나는 O(nlogn)으로 풀었는데

우선 enumerate와 sorting을 이용한 O(nlogn) 풀이입니다.

d,dist = int(input()),list(map(int,input().split()))
_ = list(map(int,input().split()))
gas = sorted([i for i in enumerate(_[:-1])],key = lambda x:x[1])
budget = 0
for city,cost in gas:
    if city<d:
        budget+=sum(dist[city:d])*cost
        d=city
print(budget)

 

enumerate를 이용해 (도시,가격) 형태로 리스트를 만들어 가격을 기준으로 오름차순 하여 정렬된 gas라는 리스트를 만들었습니다. 

그러고 반복문을 돌리게 되면 가장 저렴한 도시의 정보들을 순차적으로 반복하게 됩니다. 

변수 d는 목적지를 의미합니다. 처음 목적지는 당연히 종료 지점입니다. 

따라서 저렴한 도시가 목적지보다 작을 경우 목적지까지의 가격을 더해주게 됩니다. 그 뒤에 목적지를 바꿔주게 됩니다.

위의 예시를 다시 이용하자면 첫 반복문에서 c에서 e까지의 비용을 구하게 됩니다. 그렇게 되면 목적지는 c로 바뀝니다. d 도시의 경우 조건문에 의해 고려되지 않습니다. 

 

이 경우 마지막 도시에서 가격 정보는 필요 없어서 이를 제외해주고 리스트를 만들었습니다.

 

 

 

다음은 O(n) 풀이입니다.

도시를 순차적으로 방문하면서 방문한 도시의 기름 가격이 이전에 주유를 했던 도시보다 작을 경우 주유하는 방법입니다.

n,dist = int(input()),list(map(int,input().split()))
gas = list(map(int,input().split()))
gas[-1] = 0
budget,start = 0,0
m = int(1e9)+1
for city,cost in enumerate(gas):
    if cost<m:
        budget+=sum(dist[start:city])*m
        start = city
        m = cost
print(budget)

현재 도시의 cost가 마지막으로 주유한 도시의 가격 m보다 작을 경우에 (마지막 도시부터 지금 도시까지 거리)*m을 예산에 더해줍니다.

 

마지막 도시까지 방문할 때까지 m보다 작은 케이스가 없는 경우 엣지케이스가 발생합니다.(목적지 바로 전 마지막 도시에서 가장 저렴한 경우도 이 케이스에 포함) 해당 경우를 예외처리를 위해 마지막 도시의 가격을 0으로 설정하였습니다. 그렇게 되면 항상 마지막 도시에서 예산을 구하는 연산을 수행하게 됩니다.

 

이런 실제 코테라고 생각하면 엣지케이스가 발생하는 풀이는 별로 안좋은거 같아서 첫번째 방법이 더 안전한 풀이가 아닐까라고 생각합니다.