백준_13305 (주유소_실버4_그리디)

RostoryT·2022년 7월 5일
0

DP and Greedy

목록 보기
5/12

메모

메모한것

기름통 무제한
도로 이동할 때, 1km마다 1리터 사용

도로 위 숫자 = 길이(1km -> 1리터)
원 안에 숫자 = 리터당 가격(x원 * n리터 = xn원) => 충전하는 식으루 생각

total = 6일 때,
1. 5 6 = 30원 한번에 다 채운 경우
2. (5
2) + (2 3) + (4 1) = 20원 갈 때마다 채운 경우
3. (5 2) + (2 4) = 18원 큰값에서만 필요한만큼만 챙기고 나머진 싼데서 한번에


쌀때 많이 사두는게 그리디하게 좋음
마지막 주유소에선 사지 않는다

맨왼쪽부터 이중for문같이 갈건데
일단 맨앞에 주유소의 기름값을 가진 변수 j(=가장 싼 주유소임 -> 인덱스를?)
for(range(1, n))이동하면서 다음 주유소와 기름값 비교 -> 다다음 주유소와도 비교
(i-1 vs 1)가 아니라
(j vs i vs i+1 vs i+2 vs ... ) 인거임

핵심은 이거
road 인덱스랑 station 인덱스랑 따로 감

알고리즘 - 보지마

road[]      # range(n-1)
station[]   # range(n)
gas = 0     #<-- 충전 필요

필요한 총리터 tot_gas = sum(road)
최적의 해 ans = station[0] * tot_gas   #첫 번째 주유소에서 다 넣는 경우를 max로 넣어둠

for i in range(1, len(station)):
    # 다음 주유소가 더 싸면
    if 
        tmp = (station[i-1]*road[i-1]) + (station[i]*total)
        ans = min(ans, tmp)

print(ans)

솔루션 코드 - 17점

'''내가 푼'''
n = int(input())
road = list(map(int, input().split()))      # range(n-1)
station = list(map(int, input().split()))    # range(n)


tot_gas = sum(road)           # 필요한 총 gas 수
#ans = station[0] * tot_gas   # worst case : 첫 번째 주유소에서 다 넣는 경우 금액
gas = road[0]                # 보유 가스 (1리터에 5원 -> 2k라면 10원 필요)

min_gas_idx = 0
now_road_idx = 0
ans = 0

for i in range(1, n):
    # 다음 주유소가 더 싸면
    tot_gas -= road[min_gas_idx]
    gas -= road[min_gas_idx]
    ans += (station[min_gas_idx] * road[now_road_idx])
    
    if station[min_gas_idx] > station[i] or gas == 0:        
        min_gas_idx = i
    now_road_idx = i
    
print(ans)



솔루션 코드 - 100점

  • 코드가 지저분했다. 코드가 꼬여서 생각한건 맞았는데 답이 안나옴. 단순하게 생각하자
  • 단순하게 생각해서 min 주유소의 index를 기록해두고
    • i를 증가시키면서
    • 현재 위치 index i가 min주유소보다 작으면 값싼 주유소 위치 리뉴얼 후 += 계산
    • 맞든 아니든 (주유소[min_index] * road[i])를 += 계산
'''내가 푼 - 다시'''
n = int(input())
road = list(map(int, input().split()))      # range(n-1)
station = list(map(int, input().split()))    # range(n)

ans = road[0] * station[0]  # 무조건 계산되는 값 (for문은 비교를 위해 1부터 시작할 것임)
min_cost_idx = 0

for i in range(1, n-1):
    # 앞에 min값보다 작다면
    if station[min_cost_idx] > station[i]:        
        min_cost_idx = i
    ans += (road[i] * station[min_cost_idx])
        
print(ans)



솔루션 코드 - 다른사람 100점


profile
Do My Best

0개의 댓글