[SWEA/D2] 1859. 백만 장자 프로젝트

[문제 링크]

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

SW Expert Academy

---

[문제 설명]

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

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

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

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

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

---

[제약 사항]

---

[입력]

 

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

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

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

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

 

[출력]

 

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

---

제출 코드

t = int(input())

for i in range(1, t+1):
    n = int(input())
    
    # 입력 받은 가격을 거꾸로 저장한다
    prices = list(reversed(list(map(int, input().split()))))
    
    price = prices[0]  # 시작 가격
    buy = 0            # 총 구매 금액
    sell = 0           # 총 판매 금액
    
    for j in prices[1:]:
    	# price보다 구매가격 j가 낮으면 구매해야 함
        if j < price:
            sell += price  # 총 판매 금액에 price 더하기
            buy += j       # 총 구매 금액에 j 더하기
        # price보다 구매가격 j가 높으면 price 갱신
        else:
            price = j
    
    # 이익을 구하기 위해, 총 판매 금액에서 총 구매 금액 빼기
    print('#'+str(i), sell-buy)

 

풀이

• 아무 것도 사지 않는 케이스도 있다!
  • 10 7 6 이 입력되는 경우, 가격이 계속 떨어지기 때문에 안사고 안파는 것이 이득으로, 최대 이익은 0원이다.
• 이익을 보기 위해서는 현재 가격보다 이후 시점의 가격이 더 높아야 한다. (구매가보다 판매가가 높아야 한다)
  • 거꾸로 접근하면 계산하기 쉽다.
  • 마지막 일자의 가격을 판매금액으로 설정하고, 이전 금액에 접근해 비교해서 계산한다.
    • 판매가격 price보다 작은 값이라면 구매한다(이득볼수 있음).
    • 판매가격 price보다 큰 값이라면 판매가격을 현재 가격으로 갱신한다.

---

알아둘 사항

• 리스트를 reversed하면 reversed 자료형이 되기 때문에 슬라이싱 등 리스트 함수를 적용할 수 없다. for문을 통해 원소에 하나씩 접근은 가능하지만, 슬라이싱 등을 사용하려면 다시 list로 형변환을 해줘야 한다.