[SWEA] D2 - 1859. 백만 장자 프로젝트 in 파이썬

문제 출처

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부터 시작한다)를 출력하고, 최대 이익을 출력한다.


[예제 풀이]

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

 

---

문제 풀이

미래를 알 수 있다 = 다음 날 가격도 미리 다 알 수 있다 = 뒤에서부터 접근할 수 있다

 

다음 날 가격을 모른다면 일이 복잡해지면서 DP를 사용해야겠지만, 이번 문제는 미래를 알 수 있으므로 보다 간단하게 뒤부터 접근해서 풀 수 있다.

 

가장 많은 이익을 남기기 위해서는 살때는 싸게, 팔때는 매입한 가격보다 더 비싸게 팔아야한다.

즉, 가격 리스트에서 특정 기점과 비교하면서 높은 가격일 때는 팔고, 낮은 가격일 때에는 사야한다.

 

최대 이익을 내기 위해서는 뒤에서부터 탐색하면서, 당일이 전날보다 시세가 비싸면 당일은 판매일로, 전날은 매입날로 정하고 차익을 계산한다. 당일보다 전날 시세가 더 비싼 순간이 오면, 그 날은 매입하지않고 판매기점으로 전환한다.

이러한 일련의 과정을 리스트가 끝날때까지 반복해주면서 이익을 합산하면 된다.

 

리스트 끝부터 리스트 앞까지 반복 탐색하는 것이 복잡하면, 아예 리스트를 역순화한 뒤 역순화한 리스트의 처음부터 리스트 끝까지 순회 작업을 해주면 된다.

 

 

작성코드

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    li = list(map(int, input().split()))

    # 뒤에서 부터 편하게 탐색하기 위해 문자열 전체 역순화
    li = li[::-1]
    profit = 0
    curr = li[0]
    for i in range(1, N):
        if curr > li[i]:
            profit += (curr - li[i])
        else:
            curr = li[i]

    print(f'#{test_case} {profit}')

 

느낀 점 

이제껏 풀었던 D2문제 중 가장 어려운 문제였다. 정답률 30%인 이유가 있다.

재학시절 알고리즘 수업의 악몽이 떠올랐다. '가장 긴 막대의 길이 구하기'를 들어가기 전에 OT처럼 나왔던 내용...

그때 이해하기가 참 어려웠는데... 지금은 그때보다는 이해가 수월한 걸 보니, 어떻게든 꾸준히만 하면 느리더라도 성장하는구나 싶다.

 

 

알게된 점

[::-1]

역순으로 뒤집는 방법이 reverse() 함수만 있는 것이 아니었다.

파이썬에서는 슬라이스를 가지고 역순화시킬 수 있었다.

 

다만 둘은 차이가 있었는데,

• reverse()는 리스트에만 적용 가능한 반면,
• [::-1] 는 리스트뿐만 아니라 문자열에도 적용 가능하다. 또한 인덱스로 역순화시킬 범위도 지정할 수 있다.