Python으로 푸는 SW Expert Academy 1859. 백만 장자 프로젝트

SW Expert 아카데미 1859. 백만 장자 프로젝트 

 문제에서 원재는 미래에 물건의 매매가를 미리 보는 능력을 사용하여 물건을 미리 사재기를 하여 최대 수익을 얻으려고 한다. 

원재가 사재기를 통해 최대 이익을 얻을 수 있도록 구입과 판매를 하는 코드를 짜려면 어떻게 해야 할까.

SW Expert Academy에서 푼 문제 리스트 보기

github에서 코드 보기

문제에서 제시한 조건

1. N일 동안의 물건의 매매가를 예측하여 알고 있다.

2. 과도한 사재기 방지를 위해 하루에 최대 1만큼 구입할 수 있다.

3. 판매는 언제든지 할 수 있다.

문제 풀기 전 결정 사항

- 원재가 각각의 테스트 케이스마다 예측가능한 N일은 최대 1,000,000이며 최대 N 길이의 리스트를 생성하여 최대 매매가의 index를 찾아 그 index를 기준으로 문제를 풀어나간다.

- 모든 테스트 케이스를 입력받아서 문제를 풀면 메모리를 너무 많이 사용하므로, 메모리 사용을 줄이기 위하여 yield 키워드로 generator를 사용하여 각각의 케이스별로 input 데이터를 처리하여 결과 값을 출력한다. 

(Generator는 한번에 끝나지 않고 여러번에 걸쳐 입출력을 받을 수 있어 대용량 처리 함수 제작에 편리하다!)

문제 풀이 방법

- 최대 이익이 나는 매매가의 index를 기준으로 케이스를 나눠주어야 한다.

- start_index는 0, end_index는 테스트 케이스의 총 길이 -1 이다.

- start_index부터 end_index까지 최대 매매가를 찾는다

- 사재기를 할때의 금액, 사재기한 물건의 수를 저장해두어야 순수익을 알 수 있다.

- index 범위 내의 값 중에 최대 매매가가 없는 경우(모든 매매가가 같은 경우 포함)에는 더이상 매매를 하지 않는다. (종료한다)

case 1. 최대 매매가가 start_index인 경우.

최대 매매가일 경우에는 사재기를 하더라도 그보다 비싸게 팔아 이익을 낼 수 있는 날이 없으므로,

구매를 하지 않고 그 다음 index 부터 다시 최대 매매가를 찾는다. (start_index += 1)

case 2. 최대 매매가가 start_index가 아닌 경우.

start_index에서부터 매매를 시작하여 최대 매매가에 모두 판다.

예를 들어, 1 1 3 1 2 일 경우! index가 2일때 최대 매매가이다.

step1. index 0 ~ 1 까지 (1 1 3 1 2) 2일 동안 구매한다. (구매 비용 1 * 1 + 1 * 1 = 2)

step2. index 2일 때, 최대 매매가이므로 이때 구매해 둔 물건을 최대 매매가에 판매한다. (구매한 물건 수 : 2, 매출 : 2 *3 = 6, 기존 구매비용 : 2,  6 - 2 = 4(순수익))

step3. 순수익을 계산한다. 6(2*3) - 2( 1 * 1 + 1 * 1) = 4(순수익)

case 3. start_index가 end_index일 경우.

start_index와 end_index가 일치하는 경우 더 이상 사재기를 할 필요가 없으므로 계산을 종료하고 최종 순수익을 반환한다.

수도 코드

위에 작성한 문제 풀이 방법에 따라서 수도 코드를 작성해보면 다음과 같다.

while (start_index < end_index):

set max_index from start_index to end_index in array

if start_index and max_index are equal:

start_index += 1

else:

calculate net price

start_index = max_index + 1

return total net price

파이썬 코드

 
# 최대값의 index를 반환
def maxValueIndex(start_idx, end_idx, array):
    tempArray = array[start_idx : end_idx + 1]
    return start_idx + tempArray.index(max(tempArray))
 
 
def solve(count, array):
    start_index = 0
    end_index = count - 1
    profit = 0
 
    # 마지막 index까지 검토를 마쳤을 때 종료한다
    while start_index < end_index:
        payment = 0
        count = 0
 
        max_index = maxValueIndex(start_index, end_index, array)
        # case 1. 최대 매매가가 start_index인 경우 next index로 넘어가서 재검
        if max_index == start_index:
            start_index += 1
            continue
 
        # case 2. 최대 매매가가 start_index가 아닌 경우
        for i in range(start_index, max_index):
            payment += array[i]
            count += 1
        profit += (array[max_index] * count - payment)
        start_index = max_index + 1
 
    return profit
 
 
def gens():
    t = int(input())
    for i in range(t):
        count = int(input())
        yield count, list(map(int, input().strip().split()))
 
if __name__ == "__main__":
    num = 0
    for count, array in gens():
        num += 1
        print('#{0} {1}'.format(num, solve(count, array)))
 
 

#SW Expert Academy #백만 장자 프로젝트 Python #백만 장자 프로젝트 #1859. 백만 장자 프로젝트 #삼성 코딩 테스트 #파이썬 백만장자 프로젝트 #삼성 1859 백만장자 프로젝트 #삼성 코테 #파이썬 백만 장자 프로젝트 #1859 백만장자 python #python 1859 백만장자 #파이썬 1859 백만장자 프로젝트 #파이썬 1859 백만장자 #1859 백만장자 파이썬 #1859 백만장자 프로젝트 코드 #삼성 1859 백만장자