바위 뚫는중

[BOJ] 백준 13505 주유소 Python3 본문

Algorithms

[BOJ] 백준 13505 주유소 Python3

devran 2022. 11. 2. 15:33
반응형

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

 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

✅ 생각

제일 왼쪽 도시(5)에서 6리터를 넣고 주유 없이 쭉 가면 요금 30원 5*6 = 30

제일 왼쪽 도시에서 2리터를 넣고 그 다음에서 3리터를 넣고 그 다음도시에서 1리터를 넣으면

→ 52 + 23 + 4*1 = 20

제일 왼쪽 도시에서 2리터의 기름을 넣고, 다음 번 도시까지 이동한 후 4리터의 기름을 넣으면

→ 52 + 24 = 18

제일 왼쪽 도시에서는 무조건 기름을 넣어야 함. 첫도시 = 기준값

  1. 기준값보다 비싸면 기준값 * 거리
  2. 기준값보다 싸다면 그 도시의 값 거리*

문제풀이

  1. 도시 수 입력받기
  2. list를 이용하여 도시 사이의 거리 입력받기
  3. list를 이용하여 도시 당 기름값 입력받기
  4. 드는 총 요금을 일단 0으로 선언해주기
  5. 첫 도시에서는 무조건 기름을 넣어야 하기 때문에, 최솟값이자 기준값으로 설정하기
  6. 도시수 만큼 반복문을 수행하여 최솟값과 기름값을 비교하여 요금을 더해주기
  7. 요금 return

✅ 코드

# 도시의 수
n = int(input())
# 도시 사이의 거리 list
arr1=list(map(int, input().split()))
# 도시 당 기름 가격 list
arr2=list(map(int, input().split()))
# 총 요금
cost = 0
# 기준점이 되는 첫 도시를 min으로 설정
min_cost = arr2[0]

for i in range(len(arr1)):
    if arr2[i] >= min_cost: #첫도시보다 기름값이 비싸면
       cost+= min_cost * arr1[i] #첫도시값 * 거리
    else: #첫도시보다 기름값이 싸다면!
        min_cost = arr2[i] #이 도시를 min값으로 두고, 거리값곱하기
        cost += min_cost * arr1[i]
    
print(cost)

 

후기

다른 그리디 보다 오히려 구현은 더 쉬웠던 거 같고 흥미로웠음.

오히려 정답률이 높은 다른 문제가 더 어려웠다. 그리디에 익숙해지려면 한 30문제는 더 풀어야할듯,,

반응형