728x90

2021.12.13

백준 13305 주유소

# 13305 주유소
N = int(input())
R = list(map(int, input().split())) # 각 도시 간 거리
P = list(map(int, input().split())) # 각 도시의 기름값
del P[N-1]                          # 의미없는 마지막 값 삭제
Q = 0                               # 총 비용

while P != []:  
    sm = P.index(min(P))        # 가장 저렴한 기름값의 인덱스 
    Q = Q + P[sm]*sum(R[sm:])   # 가장 저렴한 기름값 * 이후 거리
    del P[sm:]
    del R[sm:]

print(Q)

처음 짰던 코드

반복문이 돌아가면서 리스트를 계속 확인해서 그런지 시간 초과가 떴다.

아이디어는 가장 작은 기름값이 있으면 그 뒤에 거리는 가장 작은 기름값과 거리를 곱한 

값을 할당하면 된다고 생각했다.

# 13305 주유소
N = int(input())
R = list(map(int, input().split())) # 각 도시 간 거리
P = list(map(int, input().split())) # 각 도시의 기름값
del P[N-1]                          # 의미없는 마지막 값 삭제
Q = 0                               # 총 비용
S = 1000000000                      # 기름의 초기값

for i in range(N-1):
    if S < P[i]:         # 작은 기름값이 나오면 그 기름값으로 교환
        Q = Q + S*R[i]
    else:
        S = P[i]
        Q = Q + S*R[i]
        
print(Q)

S에 10억을 할당한 이유는 기름값으로 주어질 수 있는 max값이 10억이길래 초기값으로 할당했다.

그 값을 도시의 기름값고 비교해서 S가 작으면 S와 거리를 곱해주고

S가 크면 S의 값을 P[i]값으로 바꿔준 다음 S와 거리를 곱해준다. 

반복문이지만 리스트를 한 번만 확인하면 풀린다.

728x90

'Algorithm' 카테고리의 다른 글

백준 2798 파이썬  (0) 2021.12.17
코드업(CodeUp) 3120 파이썬  (0) 2021.12.16
백준 1541 파이썬  (0) 2021.12.10
그리디 알고리즘(탐욕법)  (0) 2021.12.08
백준 11047 파이썬  (0) 2021.12.08

+ Recent posts