🐸 문제 정보
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
🤖 알고리즘
그리디
⏱️ 풀이 시간
06.23m
📝 풀이
보자마자 그리디 같다고 느껴졌다.
도시를 정방향으로 순회하면서, 주유소 리터 당 값의 최소값을 새로 갱신해준다.
현재까지 나온 리터 당 최소 값을 다음 도시로 이동하는 거리만큼 곱해서 더해준다.
간단한 그리디 문제였다.
🧑💻 나의 답
# pypy3
import sys
input = sys.stdin.readline
INF = sys.maxsize
n = int(input().rstrip())
dist = list(map(int, input().rstrip().split())) # 거리 (n - 1)
vals = list(map(int, input().rstrip().split())) # 가격 (n)
min_val = INF
res = 0
for i in range(n - 1):
min_val = min(min_val, vals[i])
res += min_val * dist[i]
print(res)'PS > 문제풀이' 카테고리의 다른 글
| 백준 15724 주지수 Python (1) | 2024.01.06 |
|---|---|
| 백준 6068 시간 관리하기 Python (1) | 2024.01.06 |
| 프로그래머스 SQL 오프라인/온라인 판매 데이터 통합하기 (0) | 2024.01.04 |
| 프로그래머스 SQL 서울에 위치한 식당 목록 출력하기 (1) | 2024.01.04 |
| 백준 1439 뒤집기 Python (1) | 2024.01.04 |