백준 13305

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

13305번: 주유소

 

---

 

풀이 1 (58점, 부분성공) - 64ms

// 도시의 수
let input: Int = Int(readLine()!)!

// 도시간 거리
var distanceArray: [Int] = readLine()!.split(separator: " ").map({Int($0)!})

// 도시의 기름값
var priceArray: [Int] = readLine()!.split(separator: " ").map({Int($0)!})

var result: Int = 0


// 마지막 도시의 기름값은 의미없음
priceArray.removeLast()


var minPrice: Int = priceArray.min()!
var firstIndex: Int = priceArray.firstIndex(of: minPrice)!

while firstIndex != 0 {
    result += distanceArray[firstIndex..<distanceArray.count].reduce(0, +) * minPrice
    
    distanceArray = Array(distanceArray[0...firstIndex-1])
    priceArray = Array(priceArray[0...firstIndex-1])
    
    minPrice = priceArray.min()!
    firstIndex = priceArray.firstIndex(of: minPrice)!
}

result += distanceArray.reduce(0, +) * minPrice

print(result)

 

 

점수로 나오는건 처음봤는데 58점이길래 당황했다; 틀리면 틀린거고 맞으면 맞는거지 이게 뭐여..?

테스트 케이스를 몇가지 시도했는데 결과가 이상하게 나오지는 않았다..

해결하는 방식이 문제(?)가 있는가보다 하고 다른사람들이 푼 방식을 보고 수정했다.

 

 

풀이 2 (100점, 성공) - 96ms

// 도시의 수
let input: Int = Int(readLine()!)!

// 도시간 거리
var distanceArray: [Int] = readLine()!.split(separator: " ").map({Int($0)!})

// 도시의 기름값
var priceArray: [Int] = readLine()!.split(separator: " ").map({Int($0)!})

var result: Int = 0

result += priceArray[0] * distanceArray[0]

var minPrice: Int = priceArray[0]

for index in 1..<priceArray.count-1 {
    if priceArray[index] < minPrice {
        minPrice = priceArray[index]
        result += minPrice * distanceArray[index]
    }else {
        result += minPrice * distanceArray[index]
    }
}

print(result)

 

 

처음 해결한 방식

1. price배열에서 min값을 찾고, 가장 싼 주유소가 있는 도시의 위치(index)를 firstIndex()로 찾아서 해당 도시부터 마지막 도시까지의 가격을 계산한다.

2. 해당 Index ~ 마지막 Index의 내용을 제외하고 배열을 업데이트한다.

3. 업데이트된 배열로 내용을 반복한다. (가장 싼 주유소의 위치가 Index 0이 나올때까지)

 

수정한 방식

1. 첫 도시에서 다음 도시까지의 필요한 기름의 양 만큼 가격을 계산한다.

2. 다음 도시의 기름값과 첫 도시의 기름값을 비교하여 더 싼 기름값으로 다음 도시까지 필요한 기름의 양 만큼 계산한다.

3. 이 과정을 반복

 

 

시간은 처음 푼 방식이 더 느릴줄 알았는데.. 조금 더 빨랐다. 

이유를 생각해보니 수정된 방식은 모든 도시마다 코드가 수행되는 반면

내가 처음 풀었던 코드는 min값이 앞에 위치할수록 수행하는 단계가 엄청 단축된다.. 아마 여기서 차이가 있는듯 ㅇㅅㅇ?

 

그런데 58점 이래니까.. 아마 어디선가 문제가 있겠지..