백준 17939번 Gazzzua 파이썬

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

 

내 코드

N = int(input())
coin = list(map(int, input().split()))[::-1]

standard = coin[0]
result = 0

for i in range(1, len(coin)):
    if standard > coin[i]:
        result += standard - coin[i]
    else:
        standard = coin[i]
        
print(result)

---

 

Review

문제에 나와있는 핵심 조건은 아래와 같습니다.

1. 구매는 매 분마다 1개씩 가능
2. 판매는 제한 없음

문제에 나와 있는 예제 1 5 10 2 4 3으로 설명하겠습니다.

언제 사고 언제 파는지에 대한 기준을 정해야 한다고 생각을 했습니다.

하지만 그냥 보면 아무것도 생각 안 나서.. 뒤집어 보겠습니다

3 4 2 10 5 1

이렇게 봤을 때, 생각나는 논리가 있었습니다.

현재 index 기준으로 오른쪽에 있는 것 중에 자기 보다 가격이 낮은 것까지 체크를 하여 수익을 계산하면 된다.
자기보다 크다면 기준을 변경하여 위 내용을 반복합니다.

그림으로 보면 아래와 같습니다.

 

이렇게 구현을 하면 시작 복잡도는 O(N)이 나오게 됩니다.
처음에는 while 문으로 풀었는데 가독성 면으로도 for문이 훨씬 괜찮은 것 같습니다.

아래는 Swift 언어 + while 문입니다.

import Foundation

let N = Int(readLine()!)!

let arr =  readLine()!.split(separator: " ")
    .compactMap { Int($0) }.reversed()
    .map { Int(String($0))! }

var index = 0
var result = 0

var standard = arr[0]

while N - index > 1 {
    
    if standard > arr[index + 1] {
        result += (standard - arr[index + 1])
    } else {
        standard = arr[index + 1]
    }
    index += 1
}

print(result)