#문제
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
#풀이 & 학습한 내용
"최소 비용으로 주유하여 일직선 도로를 달리는 문제"입니다. 처음에는 주유에 대응되는 도로를 모두 모아서 계산하는 방식으로 문제를 해결했지만, 상당히 비효율적이었고, 그저 도로마다 최소의 기름값을 곱해주어 더해주는 방식으로 변경했습니다.
#소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
N = int(input())
roads = list(map(int,input().split()))
oils = list(map(int,input().split()))
won = 0
oil = oils[0]
#도로 한개마다 계산해서 더해주기
for i in range(len(roads)):
if oils[i] <= oil:
oil = oils[i]
won += oil * roads[i]
print(won)
|
cs |
github.com/HoYoungChun/Algorithm_PS/blob/master/Greedy/BOJ_13305.py
HoYoungChun/Algorithm_PS
Baekjoon Online Judge, Programmers problem solving by Python, C++ - HoYoungChun/Algorithm_PS
github.com
'Algorithm > Greedy' 카테고리의 다른 글
| [Python] 백준 1541번 : 잃어버린 괄호 (S2) - 그리디단계별4 (0) | 2021.01.27 |
|---|---|
| [Python] 백준 11399번 : ATM (S3) - 그리디단계별3 (0) | 2021.01.27 |
| [Python] 백준 1931번 : 회의실 배정 (S2) - 그리디단계별2 (0) | 2021.01.27 |
| [Python] 백준 11047번 : 동전 0 (S1) - 그리디단계별1 (0) | 2021.01.27 |
| [Python] TCT: 왕실의 나이트 (0) | 2021.01.24 |