문제
출처 - 백준 - 13305
- 문제 접근
우리가 문제에서 구할 값은 N개의 도시의 주유소당 가격과 도시 사이의 거리를 입력받고 이를 통하여 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 구하는 것입니다.
그렇다면 어떻게 최소비용을 구할 수 있을까 고민을 해봤습니다.
문제를 풀기 위한 주된 아이디어는 여태껏 방문한 주유소의 가격들 중 가장 싼 주유소(이것을 이전 가격이라고 하겠습니다)의 가격보다 더 저렴한 주유소의 가격을 가장 가까운 오른쪽 도시에서 찾고 그 도시까지 이동할만큼의 기름을 주유해야 합니다! 최소의 비용만 구하면 되기 때문에 단순히 이전 가격보다 더 저렴한 가격의 주유소가 나오기 전까지 거리만큼 이전가격을 곱해나가면 됩니다.
코드
- 큐를 이용하지 않은 코드
import sys
from collections import deque
input = sys.stdin.readline
# n: 도시의 개수
n = int(input().strip())
# 도로의 길이
dist = list(map(int, input().strip().split()))
# 주유소의 리터당 가격
price = list(map(int, input().strip().split()))
def move():
p_price = price[0]
result = price[0] * dist[0]
for i in range(1, len(dist)):
# p_price보다 다음 주유소의 가격이 적은 경우
if p_price > price[i]:
result += (price[i] * dist[i])
p_price = price[i]
else:
result += (p_price * dist[i])
return result
result = move()
print(result)- 큐를 이용한 코드(그냥 떠올랐기에 해봤습니다!)
import sys
from collections import deque
input = sys.stdin.readline
# n: 도시의 개수
n = int(input().strip())
# 도로의 길이
dist = list(map(int, input().strip().split()))
# 주유소의 리터당 가격
price = list(map(int, input().strip().split()))
def move2():
# 큐에는 이전 도시에서의 최소가격을 저장
queue = deque()
result = price[0] * dist[0]
queue.append(price[0])
idx = 1
while idx < len(dist):
p_price = queue.popleft()
if p_price > price[idx]:
p_price = price[idx]
result += p_price * dist[idx]
else:
result += p_price * dist[idx]
queue.append(p_price)
idx += 1
return result
result1 = move2()
print(result1)-
1번 코드에서의 핵심!! : 순차적으로 탐색하면서 저렴한 가격의 주유소가 나오면 p_price를 갱신해나가면서 dist원소와 곱하여 result에 더해나간다.
-
2번 코드에서의 핵심!! : 1번 코드와 매커니즘은 똑같지만 단순히 p_price를 queue에 넣었다가 뺐다가 하는 방식으로 했습니다...(1번코드에 쓸데없는 동작을 넣은것임.. ㅡㅡ)
- 후기
답을 도출해내기 위해서 큐를 이용해볼까? 했지만 큐를 이용해도 문제를 푸는데 문제는 없었지만 단순 for문으로 탐색하는것에 비해 더 시간이 오래걸려 비효율적이였습니다!
이유는????
큐에 값을 넣고 빼고 하면서 시간이 추가적으로 걸렸다는 점입니다. 아직 자료구조를 활용하는데 있어 미숙함이 있어서 써볼까? 하면서 떠올렸더니 이 문제에서는 별로 안좋았습니다.. 큐는 하나의 값만 저장할 경우는 쓰지 않는것이 좋고 큐에 여러 값들을 넣어 순차적으로 처리할 때 사용해야 합니다!
큐에 하나만 저장된다면 큐는 FIFO(First In First Out)의 특징을 갖기 때문에 먼저 들어온 순서! 대로 처리하기 때문에 하나만 저장하는 큐의 경우는 순서는 당연히 하나만 저장된 값이기 때문에 사용에 의미가 없습니다! 이제야 깨달았다니..
