[백준 13305번 / 실버4] 주유소 - (그리디)

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

13305번: 주유소

 

처음에 풀때 시간초과가 떠서 input()을 sys.stdin.readline()으로 바꿨는데 마찬가지로 시간초과가 떴다.

한마디로 코드에 문제가 있었다는 뜻.

 

아래 코드는 다시 짠 코드임.

이 문제의 풀이법!!!

 

• 현재상황에서 가장 최선의 선택을 하면 되는 그리디 알고리즘 문제이다.
• 현재 도시를 기준으로 현재 도시보다 기름값이 더 싼 곳에 이동할때까지 현재 도시에서 주유한 기름으로 이동하면 된다.
• 한마디로 반복문을 돌리면서 현재 도시보다 기름값이 더 싼 도시가 나올때까지 현재 도시의 기름으로 이동하는 것이다.

import sys

n=int(sys.stdin.readline())
road=list(map(int,sys.stdin.readline().split()))
price=list(map(int,sys.stdin.readline().split()))
result=0

i,result,length=0,0,len(road)
while i<length:
  const=price[i]
  while const<=price[i] and i<length:
    result+=const*road[i]
    i+=1
print(result)
  

코드를 짜놓고 보니 while문 안에있는 저

i<length

이 조건이 중복해서 들어있는게 너무 거슬렸다.

그래서 코드를 다시한번 다듬어 보았다.

아래는 최종 코드!!

 

import sys

n=int(sys.stdin.readline())
road=list(map(int,sys.stdin.readline().split()))
price=list(map(int,sys.stdin.readline().split()))
i,result,length=0,0,len(road)
const=price[0]
while i<length:
  if const>price[i]:
    const=price[i]
  result+=const*road[i]
  i+=1
print(result)

훨씬 더 깔끔~