11501. 주식

11501 문제 보기

Difficulty : Silver 2

Status : Failed

Time : 00:29

접근 방식

오답 접근 방식

정답을 봤을 땐 정말 간단하게 풀이할 수 있는 문제인데,
확실히 문제를 계속 풀어나가려는 지구력과 적용하려는 알고리즘을 구조화해 생각하지 않는 것이 코테 실력이 늘지 않는다고 느끼는 이유인 것 같다 흐밍 🙀

문제 풀이를 보고 그리디로 판단한 후 처음 접근했던 방식은 다음과 같다.

- 다음 날 가격이 더 높다면 -> 사기
- 이전에 주식을 샀으나 다음 날 가격이 더 작다면 -> 팔기
- 계속해서 다음 날 가격이 더 낮다면 사지 않기

케이스를 나누는 것에서 약간 핀트가 어긋났기에 예외 조건에 대한 처리 역시 조금씩 틀어졌다.

정답을 위한 접근 방식

케이스를 다음과 같이 나누면 됐다.

1. 주가가 오를 때, 주식 사기
2. 주가가 떨어질 때, 주식 팔기

[1, 1, 3, 1, 2] 예제 입력을 보면,
처음 두 날에서 주가가 유지되다가 셋째 날 주가가 오르므로 처음 두 날은 주식을 산다.
셋째 날과 넷째 날을 비교했을 때, 주가가 떨어지므로 셋째날 주식을 판다.

역으로 생각해보면,
가장 마지막 날의 주가를 max로 설정하여 그 이전 날 주가가 더 높다면 max값을 갱신한 뒤, 주식을 사고 파는 여부를 결정하면 쉽게 풀이할 수 있었던 문제다.

따라서 주가를 거꾸로 정렬한 채,
주가가 떨어지는 경우, 떨어진 주가만큼을 이익으로 총액에 더해줬다.

[1, 1, 3, 1, 2]의 예제로 동작 방식을 살펴보면 다음과 같다.

최종 코드

import sys
input = sys.stdin.readline

T = int(input().rstrip())
for _ in range(T):
  N = int(input().rstrip())
  cost = list(map(int, input().rstrip().split()))
  cost.reverse()
  max_cost = cost[0]
  total = 0

  for i in range(1, N):
    if max_cost < cost[i]:
      max_cost = cost[i]
      continue
    total += max_cost - cost[i]
  print(total)

배운점

▶️ 꾸준히 한 문제 파고드는 힘 기르기 (정답 좀 보지마악!!!)