[Python] SWExpert - 백만 장자 프로젝트(D2)

문제출처 - https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

SW Expert Academy

틀린 풀이

t = int(input())

for a in range(t):
    n = int(input())
    future = [int(x) for x in input().strip().split()]
    answer = 0

    increase = 0
    cnt = 0
    for i in range(1, len(future)):
        # print(cnt, increase, answer)

        if future[i-1] > future[i]:
            if increase != i-1:
                answer += cnt * future[i-1]
            cnt = 0
            increase = i
            continue

        cnt += 1
        answer -= future[i-1]

    if cnt != 0:
        answer += cnt * future[n-1]

    print("#%d" % (a+1), answer)

처음엔 just 현재값이 바로 전보다 작으면 팔고 값 초기화하게 구현했다.

전의 값보다 크면 계속 샀다.

여기서 내가 고려하지 않은 것은 [1, 3, 2, 1, 4]에서 2일때도 샀다가 4일때 팔면 이득이라는 것이다.

 

 

통과한 풀이

t = int(input())

for a in range(t):
    n = int(input())
    future = [int(x) for x in input().strip().split()]
    answer = 0

    while True:
        if len(future) == 0:
            break
        maxPriceIdx = future.index(max(future))
        print(future, maxPriceIdx)

        for i in range(maxPriceIdx):
            answer -= future[i]
        answer += maxPriceIdx * future[maxPriceIdx]
        future = future[maxPriceIdx+1:]


    print("#%d" % (a+1), answer)

설명

 

1. 현재 배열에서 가장 큰 값을 찾고

2. 그 전의 값들을 산 다음에 작은 값들의 개수만큼 answer에 더해준다.

3. 배열에서 max값까지 모든 값들을 없애주고 다시 max값을 찾는다.

4. 배열이 빌때까지 반복한다.