https://www.acmicpc.net/problem/13305
1. 문제 설명
도시 개수, 도시 별 1리터 당 기름 가격, 도시에서 도시 사이의 거리를 입력받아 주유비의 최솟값을 구하는 문제다.
2. 풀이
첫 번째 시도(17점)
1. 어차피 마지막 도시에서는 더 가지 않으니 가격을 생각하지 않았다.
2. price의 최솟값을 구해 그 도시부터 마지막 도시까지 가는 거리를 더했다.
3. 최솟값 도시가 오기 전까지는 반복문을 돌면서 다음으로 갈 도시의 거리와 현재 도시 가격을 더했다.
A=int(input())
distance = list(map(int, input().split()))
price = list(map(int, input().split()))
price = price[0:-1] #마지막 도시는 어차피 더 갈 곳이 없으니 제외
min_price = price.index(min(price))
answer = price[min_price]*sum(distance[min_price:])
for i in range(min_price):
answer += price[i]*distance[i]
print(answer)
그런데 이렇게 푸니 서브태스크 1번만 통과했다.
A=int(input())
distance = list(map(int, input().split()))
price = list(map(int, input().split()))
min_price = price[0] #최소 가격을 첫 번째 인덱스로 설정
answer = 0
for i in range(A-1): #마지막 인덱스 제외하고 반복문 수행
if min_price>price[i]: #현재 인덱스값이 최솟값보다 작으면 min_price 바꿔줌
min_price = price[i]
answer+=min_price*distance[i] #현재 인덱스 거리값과 최솟값을 곱해줌
print(answer)
위 로직으로 바꾸어주니 100점을 맞을 수 있었다.
1. 처음에는 무조건 충전을 해야 하니 최소 가격을 첫 번째 인덱스로 설정해준다.
2. for문을 돌면서 현재 최솟값보다 현재 인덱스 값이 더 작으면 최솟값을 바꿔준다.
3. 최솟값과 거리를 곱한다.
처음에는 최솟값을 구하고, 최솟갑 인덱스부터 끝까지의 거리를 곱한 후, 앞의 인덱스 값들을 계산해주었고, 두 번째는 앞에서부터 최솟값을 찾아가면서 값을 구해주는 방식이다.
가격이 5,2,3,4,1 이런 식으로 있을 때, 처음에는 가격 5로 첫 번째 거리만큼을 충전하고, for문을 돌면서 최솟값이 2로 바뀐다. 이후 도시들을 갈 때 최솟값이 유지되기 때문에 가장 싼 가격으로 충전을 할 수 있게 된다.
728x90
'study > 알고리즘' 카테고리의 다른 글
[알고리즘] 정렬 알고리즘(이것이 코딩테스트다) (0) | 2024.05.20 |
---|---|
[알고리즘] '이것이 코딩테스트다' Chapter 4 구현 (1) | 2024.05.06 |
[백준] 백준 11047 <동전 0> 파이썬 (그리디 알고리즘) (0) | 2024.04.09 |
[알고리즘] 그리디 알고리즘이란? (0) | 2024.04.08 |
[파이썬] 파이썬 문법 정리 (1) | 2024.04.01 |