반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
Tags
- express
- 백준
- 파이썬데이터분석라이브러리
- 백준 전쟁 파이썬
- 피아노체조 파이썬
- 백준 점프
- 백준알파벳파이썬
- 프로그래머스
- 파이썬 평범한배낭
- 백준 예산
- MySQL완전삭제
- 백준 피아노체조
- 소프티어 지도자동구축
- MongoDB
- CRUD
- express mongodb
- 소프티어 장애물인식프로그램
- 등수매기기 파이썬
- 백준 점프 파이썬
- jenkins
- 금고털이 파이썬
- 백준 전쟁-전투
- 백준 바이러스
- 지도자동구축 파이썬
- 백준 평범한배낭
- 1987파이썬
- 장애물인식프로그램 파이썬
- 백준 A->B
- 백준 등수매기기
- 도커 컨테이너
Archives
- Today
- Total
바위 뚫는중
[BOJ] 백준 13505 주유소 Python3 본문
반응형
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
제일 왼쪽 도시에서는 무조건 기름을 넣어야 함. 첫도시 = 기준값
- 기준값보다 비싸면 기준값 * 거리
- 기준값보다 싸다면 그 도시의 값 거리*
✅ 문제풀이
- 도시 수 입력받기
- list를 이용하여 도시 사이의 거리 입력받기
- list를 이용하여 도시 당 기름값 입력받기
- 드는 총 요금을 일단 0으로 선언해주기
- 첫 도시에서는 무조건 기름을 넣어야 하기 때문에, 최솟값이자 기준값으로 설정하기
- 도시수 만큼 반복문을 수행하여 최솟값과 기름값을 비교하여 요금을 더해주기
- 요금 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문제는 더 풀어야할듯,,
반응형
'Algorithms' 카테고리의 다른 글
[BOJ] 스택문제 - 9012 괄호, 10828 스택, 10773 제로 Python3 (0) | 2023.01.27 |
---|---|
[Algorithms] 자료구조 - 선형구조 / 비선형구조 (2) | 2023.01.27 |
[BOJ] 백준 11047 동전 Python3 (0) | 2022.11.02 |
[Algorithms] 그리디 알고리즘 Greedy Algorithm - 탐욕 알고리즘 (0) | 2022.11.02 |
[BOJ] 백준 7568 덩치 Python3 (0) | 2022.10.20 |