백준 - 13305(그리디 알고리즘)

import sys
n = int(sys.stdin.readline())

road = list(map(int, sys.stdin.readline().split()))
road.append('a')
price = list(map(int, sys.stdin.readline().split()))

ans = 0
temp = price[0]


for i in range(0, n):
    if price[i] < temp:
        temp = price[i]

    if road[i] != 'a':
        ans = ans + (temp * road[i])
    elif road[i] == 'a':
        ans = ans + 0

print(ans)

sort가 필요하지 않은 그리디 알고리즘 문제였다.

 

한 줄 풀이 : 가장 저렴한 가격을 기억해 두고 있다가 더 저렴한 가격이 나오면 temp 값을 바꿔서 계산

 

처음에 부분 점수를 받았는데 수정한 부분들은 다음과 같다.

1. temp에 첫 번째 가격을 넣어준다.

2. price[i] <= temp에서 =을 빼서 불필요한 연산을 줄였다.

3. 반복문에 오류가 나지 않기 위해(try, except 문을 쓰지 않기 위해) road의 마지막에 문자열을 하나 추가한다.

4. 문제를 이해하고 temp의 값만 조건에 맞게 잘 바꿔주면 쉽게 풀리는 문제였다.