미소를뿌리는감자의 코딩
[백준 2024/02/23] 13305번 주유소 본문
728x90
https://www.acmicpc.net/problem/13305
1. 접근 방법
값이 싼 주유소에 대해서 오름차순 정리를 한 후,
처음에는 값이 싼 주유소에 대해서 뒤에 있는 거리들까지 기름을 채우고 이동하는 식으로 식을 구성했었다.
하지만, 시간초과가 났었다.
시간 초과가 난 코드는 아래와 같다.
len_city = int(input())
d = list(map(int, input().split()))
city = list(map(int, input().split()))
city_w_index = [[money, city_num] for city_num, money in enumerate(city)]
#print(city_w_index)
city_w_index.sort()
#print(city_w_index)
visited = [False]*(len_city+1)
total = 0
for m, c in city_w_index:
if all(visited):
break
if visited[c]:
continue
for i in range (c+1, len(city), 1):
if not visited[i]:
total += d[i-1] * m
visited[i] = True
그래서 방식을 바꾸었다.
순서대로 장소를 방문한 후, 방문한 곳의 기름값을 visited_city라는 리스트에 정리해 두었다.
이후, 새로운 장소에 방문할 때마다 현재까지 저장된 기름값들 중 최솟값을 찾고, 해당 최솟값에 대해서 다음 거리를 곱해주었다.
아래 예제를 통해서 더 깊게 이야기해 볼 것이다.
[2, 3, 1] # distance를 저장한 리스트
[5, 2, 4, 1] # 해당 위치의 기름값을 저장한 곳
이런식으로 저장하였다.
5 -> 2 -> 4 -> 1로 방문을 하였다.
우선 visited_city.append(5) 를 해주었다.
이후 min(visited_city) 를 통해 5를 찾아주었다. 2*5를 해서 total이라는 곳에 더해주었다.
이후 다음으로 2에 방문해서, visited_city.append(2) 를 해주었다.
min(visited_city) 를 통해서 2를 찾아주었고, 2*3 을 total에 더해주었다.
이런식으로 접근하였다.
2. 코드
def min_total_cost(len_city, city,d):
visited_city = []
total = 0
for i in range(0, len_city-1, 1):
visited_city.append(city[i])
total += d[i] * min(visited_city)
return total
def main():
len_city = int(input())
d = list(map(int, input().split()))
city = list(map(int, input().split()))
print(min_total_cost(len_city, city, d))
if __name__ == '__main__':
main()
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/02/23] 2212번 센서 (0) | 2024.02.23 |
---|---|
[백준 2024/02/23] 11000번 강의실 배정 (0) | 2024.02.23 |
[백준 2024/02/23] 11399번 ATM - python ver. (0) | 2024.02.23 |
[백준 2024/02/23] 1946번 신입 사원 (0) | 2024.02.23 |
[백준 2024/02/22] 1002번 터렛 - python ver. (0) | 2024.02.22 |