11501: 주식(Python)

문제접근

이 문제도 회의실 배정과 마찬가지로 그리디 접근 방법으로 풀어야 하기 때문에 명쾌한 테스트 케이스 증명이 아닌 그럴듯한 가설을 세우고 코드를 돌려보며 검증하는 방식으로 접근해야 했다. 회의실 문제와 다르게 시간순으로 정렬된 배열이기에 멋대로 배열의 순서를 바꿨다가는 대참사가 일어날 것 같아 정렬은 사용하지 않았다. 시간 제한은 5초지만 테스트케이스 배열의 길이가 (2 ≤ N ≤ 1,000,000) 라 시간이 넉넉하다고도 볼 수 없었다. 

 

우선 1) 미래의 가격을 예측할 수 있다는 가정 하에 거래하고, 2) 단순하게 가지고 있는 현재의 주식을 모두 파는 것이 아니라 원하는 만큼 팔 수 있다는 점에 주목했다. 그런데 조금 생각해보니 미래를 예측할 수 있다는 가정이 있으니 주식의 가격이 내리면 사고, 오르면 앞으로 더 오를지 판단하여 더 오르면 팔지 않고 더 이상 오르지 않으면 다 팔아버리면 그만이기 때문에 2번째는 고려할 필요가 없었다. 이제 여러 변수(주식 잔고, 총액, 총 이익)를 세팅하고 변수 값을 변경해가며 1) 사거나 2) 모두 팔거나 둘 중 하나의 행동을 반복했다. 아래는 정답 코드이다. 

 

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    days = int(sys.stdin.readline())
    prices = list(map(int, sys.stdin.readline().split()))

    stocks = 0
    total = 0
    benefit = 0
    for i in range(days):
        buy = False
        for j in range(i + 1, days):
            if prices[j] >= prices[i]:
                buy = True
                break
        if buy:
            stocks += 1
            total += prices[i]
            continue
        benefit += prices[i] * stocks - total
        total, stocks = 0, 0
    print(benefit)

마치며

탐욕적 기법이라는 이름에 걸맞게 얼마나 더 탐욕스럽게(?) 야비하게(?) 보다는 현명하게 가설을 세우고 검증하는지가 중요한 테마인 것 같다. 계산 과정이 복잡한 로직을 짜는 것이 아니라, 문제에 숨겨진 조건을 잘 찾아내고 적용하는 것이 관건인 것 같다.