[백준] 17521번 Byte Coin 파이썬 정답 코드

17521번: Byte Coin

---

1. 문제 내용

 

 

2. 접근 방식

• 최대 수익은 극소값에서 사고, 극대값에서 팔기를 반복하면 된다.

극소값은 함수가 감소에서 증가로 바뀌는 지점이고, 극대값은 증가에서 감소로 바뀌는 지점이다.

 

• 코인을 사고 팔 때, 현재 가지고 있는 coin 개수와의 연관 관계

s 리스트를 순환하면서 언제가 극대값이고, 언제가 극소값인지 파악을 하기 위해선 coin 개수를 함께 고려해야 한다.

위 그래프로 예시를 들어보자. 극소값이 4일째인 2라는 것을 금방 알 수 있지만, 코드로는 2가지 조건으로 표현할 수 있다. 1) 4일째 값인2 보다 5일째 값인7이 더 크다. 2) 기존에 보유한 coin 개수가 0이다. 즉, 코인 개수가 0이면서 다음 날 값이 더 비싸야 그 날이 극소값이다. 

 

 

3. 정답 코드

n, w = map(int, input().split())
s = [int(input()) for _ in range(n)]

# 극대값에서 팔고, 극소값에서 사기를 반복
i = 0
coins = 0
while i < n-1:
    if s[i] < s[i + 1] and coins == 0:
        coins = w // s[i]
        w = w % s[i]

    if s[i] > s[i + 1] and coins != 0:
        w += coins * s[i]
        coins = 0

    i += 1

if coins:
    w += coins * s[i]

print(w)

기존엔 극대값과 극소값일 때의 인덱스를 ups와 donws라는 각각의 리스트에 담고, 그 둘을 다시 vertices 리스트로 합치고. ups 리스트가 비었을 때, downs 리스트가 비었을 때를 따로 구분하고... 등등 매우 지저분하고, 비효율적인 로직으로 오답인 코드를 작성했었다. 이에, 아예 새로운 로직을 고민하던 중 coin 개수를 활용하는 방법이 번뜩 떠올랐고, 덕분에 문제를 해결할 수 있었다.