[Baekjoon/백준] 13305번 Python

문제 출처 : www.acmicpc.net/problem/13305

13305번: 주유소

1 . 문제 접근 방식

- 그리디 알고리즘의 대표적인 방법이라고 할 수 있다. 그리디 알고리즘이란 경우의 수가 많은 경우 가장 최적의 답을 선택해서 진행하는 방식을 말한다. 

먼저, 기름값을 가장 핵심으로 생각했다. 출발 시에는 어쩔수 없이 주유를 하고 출발해야하지만 분명 기름값이 더 싼 곳은 존재할 것이다. 이를 이용하여 기름값의 배열을 돌며 작아질 경우에는 기름값을 재할당하며 거리와 곱하면서 총 비용을 구하는 방식을 사용하였다.

 

2 . 내가 푼 코드

import sys

N = int(sys.stdin.readline())

# 거리 list 입력 받기 (N-1개)
dis = list(map(int, sys.stdin.readline().split()))
# 기름값 입력 받기 (N개)
oil_price = list(map(int, sys.stdin.readline().split()))

# 처음 출발할 때의 기름값[0]
start = oil_price[0]

# 총 기름값
sum = 0

# 오일 값의 리스트를 돌며 작아지는 경우 다시 가격 구하기
# 매번 작은 기름값을 저장해두고 사용
for i in range(len(dis)):
    if oil_price[i] < start:
        start = oil_price[i]
    sum += start * dis[i]

print(sum)

 

3 . 결과 및 느낀점

- 성공! 이 전 코드들은 모두 input() 방식으로 입력을 받았다. 하지만 다은하게(daanist.tistory.com/)님의 블로그를 보던 중 sys.stdin.readline()방식을 이용하여 입력을 받을 경우 코테에 더 용이하다는 글을 보았고 바로 응용해 보았다.

- input()방식과 sys.stdin.readline()방식의 차이가 궁금한 경우 이전글(naekang.tistory.com/21)을 참고하면 좋을 것 같다.