[SWEA 1859번] 백만 장자 프로젝트 (파이썬 풀이)

문제 바로 가기 

SW Expert Academy

 

🤔 문제 설명 및 입출력

---

 

✍ 접근 방법

---

최초에는 리스트의 앞에서부터 순회하면서, 오늘의 가격이 내일보다 싸다면 구매하고, 아니면 파는 방식으로 구현하려고 했는데, 왠지 단타 한번 쳐볼라고 깝죽대는 내 모습인거 같아서 관뒀다. 그리고 앞에서부터 순회하면 시간 초과가 났다.

 

하지만 전체 리스트를 순회해야하지 않고서는 문제를 해결할 수 없다고 생각했다. 그래서 발상을 바꿔서, 뒤에서부터 살펴보는 방안을 생각해보았다. 앞에서부터 살핀다면, 오늘보다 비싼 가격이 나올 때까지 값을 계속 저장하고 있어야하는데, 뒤에서부터 살핀다면 지금보다 가격이 낮았을 때만을 찍어서 보면 되니까 훨씬 간단할 것 같다는 생각에서였다.

 

그리고 이 생각은 멋지게 들어맞았다.

 

 

👨‍💻 소스 코드

---

• 파이썬

for tc in range(1 ,int(input())+1):
    N = int(input())
    sise = list(map(int, input().split()))

    # 뒤에서부터 순회
    idx = len(sise) - 1
    money = 0

    while idx > 0:
        # 전날 ~ 첫날 가격 확인
        for i in range(idx-1, -1, -1):
            # 전날 가격이 현시점보다 낮다면, 시세차익을 얻는다.
            if sise[idx] > sise[i]:
                money += sise[idx] - sise[i]
            # 가격이 더 높은 날이 있다면, idx를 변경한다
            else:
                idx = i
                break
        # 현시점 기준 과거의 가격이 모두 낮으면, 검사가 완료되었고 더 이상 확인할 필요가 없다
        else:
            break

    print('#{} {}'.format(tc, money))

 

 

🔥 강평

---

D2 난이도이긴 하지만, 생각할 거리가 많은 문제였다. 몇몇 문제들은 이 문제처럼, 앞이 아닌 뒤에서부터 살펴야지 더 쉽다. 그러니, 문제를 풀다가 막힌다면, "뒤에서부터 생각해서 문제를 풀 수 있을까?" 라는 물음을 스스로에게 던져보자