문제가 길어지면 처음엔 숨이 턱 막히는 느낌이 든다.
막상 천천히 요구사항을 읽어보고 부족한 이해는 테스트케이스를 보면 괜찮은데 말이다.
그런데 문제가 길어지면 문제를 풀때 놓치는 부분이 있을 수 있고 그러면 긴 문제를 다시 읽어봐야하는 문제가 생긴다.
그래서 긴 문제가 나오면 중요한 요구사항을 에디터에 메모하는 습관이 생겼다.
이 문제를 풀때 이해하면서 작성해놓은 요구사항이다.
- 1km가는데 1L가 필요하다.
- 출발할때 첫번째 도시에서 주유하고 출발해야한다.
- 입력 순서: 도시 개수, 도시간 거리, 도시의 기름값
- 출력 : 최소 비용 주유값
동적 계획법 (DP)
처음에 드는 생각은 각 도시까지의 최소 비용을 저장해놓고 다음 도시까지의 최소 비용을 계산할 때 사용하는 동적 계획법 비슷한 생각을 해보았다.
핵심: 가장 싼 주유소가 나오면 더 싼 주유소가 나오기 전까지 최대한 많이 주유한다.
import sys
input = sys.stdin.readline
n = int(input()) # 도시 개수
km = list(map(int,input().split())) # 다음 도시까지의 거리 (n-1개)
oil = list(map(int,input().split())) # 해당 도시의 리터당 기름 가격
min_cost = float('inf')
dp = [0 for _ in range(n-1)] # 이전 최소비용 저장할 리스트
dp.append(km[0] * oil[0])
for i, (k,cost) in enumerate(zip(km,oil), 1):
if cost < min_cost:
min_cost = cost
dp[i] = dp[i-1] + min_cost * k
print(dp[n-1])코드 설명
- dp의 초기값 설정
: 최소 다음 도시까지 갈 수 있는 기름을 주유해야함- 반복문: 각 도시까지 거리와 리터당 가격 두개의 리스트를 같이 반복
- 각 도시까지 최소비용을 저장 할 해당 dp 리스트의 인덱스에 접근하기 위해 enumerate를 1부터 시작하도록 설정함
풀면서 단순히 이전값에서 참조하는거면 굳이 dp 리스트를 사용하지 않아도 된다고 생각했다.
탐욕법 (Greedy)
import sys
input = sys.stdin.readline
n = int(input()) # 도시 개수
km = list(map(int,input().split())) # 다음 도시까지의 거리 (n-1개)
oil = list(map(int,input().split())) # 해당 도시의 리터당 기름 가격
min_cost = float('inf')
answer = 0 # 이전값 저장
#그리디
for k,cost in zip(km,oil):
if cost < min_cost:
min_cost = cost
answer += min_cost * k
print(answer) 바뀐점은 그냥 answer 라는 변수에 이전까지의 값을 저장해놓는것이다.
실행 시간 차이
124ms < 108ms 으로 두번째 코드가 더 빠르다.
(리스트에 쓰기,읽기와 enumerate 차이 인데 데이터 크기가 큰지 꽤 차이가 난다. )
