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 |