[SWEA] 1859. 백만 장자 프로젝트 - Python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc 

SW Expert Academy

 

< 📝 문제 >

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

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

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

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

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

 

다.

< ❓ 생각 >

1.

2.

< 💻 코드 >

1.

# 테스트 케이스 수
T = int(input())
for tc in range(1,T+1):
    # 연속 N일 매매가 예측 가능
    N = int(input())
    # N일간 매매가
    arr = list(map(int,input().split()))
    
   	# profit : 이익의 합, s = 시작인덱스, maxI : 구간에서 가장 큰 값을 가지는 것의 인덱스
    profit = s = maxI = 0
    while s < N:
        maxI = s
        # 구간 내 가장 큰 값의 idx 찾기
        for i in range(s,N):
            if arr[maxI] < arr[i]:
                maxI = i
        # 이익 += 최댓값 - 자신
        for j in range(s,maxI):
                profit += arr[maxI] - arr[j]
        # 구간 시작점 변경
        s = maxI + 1
    print(f'#{tc} {profit}')

2.

# 테스트 케이스 수
T = int(input())
for tc in range(1,T+1):
    # 연속 N일 매매가 예측 가능
    N = int(input())
    # N일간 매매가
    arr = list(map(int,input().split()))
    
    profit = 0
    # 마지막 값을 최댓값으로 두기
    maxI = N-1
    # 앞으로 이동하면서 최댓값보다 큰 값이 나타나면 변경
    for i in range(N-2,-1,-1):
        if arr[maxI] < arr[i]:
            maxI = i
        # 그 사이 나타나는 값들의 이익 구하기
        else:
            profit += arr[maxI] - arr[i]
    print(f'#{tc} {profit}')