백준/ Silver 4 문제 , 백준 파이썬 13305 , 주유소

백준/ Silver 4 문제 , 백준 파이썬 13305 , 주유소

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
최악의 케이스를 따로 분류하여 품

 

<문제 출처>

 

https://www.acmicpc.net/problem/13305

13305번: 주유소

------------------------------------------------------------------------------------------------------------------------------

 

 

최악의 케이스는 비용 리스트가 내림차순으로 정렬된 상태이다.

 

아마 이 케이스 때문에 처음에 제출했을때 58점이 나온 것 같다.

 

그래서. 

 

 

내림차순인지 확인하는 if 문을 만들어 주었고, 최악의 케이스인 경우 경로 길이와 가격을 인덱스에 맞게 곱해 합산해 주었다.

 

이외의 케이스들은 가장 낮은 기름 값을 찾은 뒤 그 기름 값에 해당하는 인덱스 부터의 경로는 모두 더해 싼 기름값으로 해결하였다.

 

쉽게 말하면 가장 싼 기름값의 오른쪽에 해당하는 경로의 길이는 가장 싼 기름값으로 다 해결하면된다.

 

이후 왼쪽의 경로들로만 초기화해주고 위 과정을 반복한다.

 

그러다보면 모든 경로의 가격이 측정되고 리스트값이 남지 않을 때 break 를 통해 빠져나온다.

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

N=int(input())
road=list(map(int,input().split()))
city=list(map(int,input().split()))
result=0
c=sorted(city, key=lambda x:-x)

if city==c:
    for i in range(len(road)):
        result+=road[i]*city[i]
    print(result)
else:
    while True:
        tmp=min(city)
        for i in range(len(city)):
            if city[i]==tmp:
                s=sum(road[i:])
                result+=(s*tmp)
                del(city[i:])
                del(road[i:])
                break
        if len(city)==0:
            print(result)
            break