https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

문제 설명

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.

다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.

다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.

예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,

둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

각 날의 매매가는 10,000이하이다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

[예제 풀이]

1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.

2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.

입력

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

출력

#1 0
#2 10
#3 5

---

풀이

# 최고가 날 순수익(이전날 매입개수*최고가) - 이전날 매입가격
# 1 2 3이면 순수익6 - 이전날 매입가격3
# 이전날 매입개수는 현재 인덱스
for i in range(1, int(input())+1):
    N = input()
    prices = list(map(int, input().split()))
    print(f"#{i}", end=' ')
    total = 0

    while prices:
        m = max(prices) #최대값 찾기
        m_index = prices.index(m) #최대값 인덱스
        if m_index == 0: #최대값이 첫번째에 있으면
            del prices[:m_index+1] #넘겨버리기
        else:
            total += m_index * m - sum(prices[:m_index])
            del prices[:m_index+1]

    print(total)

최대값을 찾아 최고가 날 순수익(이전날 매입개수*최고가) - 이전날 총 매입가격을 계산하여 total에 더하고 리스트에서 최고가까지의 원소들을 지워버린다.

만약 최대값이 0번 인덱스에 있다면 리스트에서 지워서 무시한다.

결과

후기

풀이 생각하느라 시간을 좀 많이 써버린 문제다...
처음에 생각한 풀이는 너무 복잡했다. 복잡할수록 답이 아니라던데 이 문제 풀면서 또 깨달음

구글링 욕구를 꾹 참고 스스로 풀어내어 참 뿌듯하다ㅎㅎ