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

문제

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.
다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.

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

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

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

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,
둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
각 날의 매매가는 10,000이하이다.

 

출력

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

 

예제

[입력]	[출력]
3 3 10 7 6 3 3 5 9 5 1 1 3 1 2	#1 0 #2 10 #3 5

 

예제 풀이

1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.
2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.

 

 

문제 해결 방법

처음에 제출 했던 코드

• 맨 처음에는 2중 for 문을 이용하여 숫자들이 담긴 배열(@num_list@)의 첫 번째 요소부터 마지막 요소까지 순회하면서 값의 차이의 최댓값의 합들을 @answer@ 변수에 넣는 방식으로 문제를 해결 하려고 하였으나, 10개의 테스트 케이스 중 7개의 테스트 케이스만 성공할 수 있었다. (나머지 테스트 케이스는 시간 초과 문제로 해결할 수 없었다.)

T = int(input())

for test_case in range(1, 1 + T):
    N = int(input())

    num_list = list(map(int, input().split()))

    answer = 0
    for i in range(0, len(num_list)):
        num_diff = 0
        num_max = 0

        for j in range(i + 1, len(num_list)):
            num_diff = num_list[j] - num_list[i]

            if num_max <= num_diff:
                num_max = num_diff
            
            # print(f"{num_list[i]} {num_diff} {num_max}")
            
        if num_max <= 0:    # 음수이거나 0일 경우
            num_max = 0
        
        answer += num_max


    print(f"#{test_case} {answer}")

 

개선한 코드

• 숫자들이 담긴 배열 안의 요소들을 역순으로 순회하면서 (@num_list[::-1]@) 최댓값 갱신과 차이값 갱신을 동시에 진행해준다. (2중 for 문을 사용하지 않고도 최댓값 갱신과 차이값 갱신을 동시에 진행할 수 있다.)
• 차이값 갱신을 할 경우, 그 결과값을 @answer@ 변수에 넣어주고, 최종적으로 @answer@ 변수의 내용을 출력해준다.

 

코드

T = int(input())

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

    answer = 0
    num_max = 0

    for num in num_list[::-1]:    # 역순으로 조회
        if num_max <= num:
            num_max = num     # 최댓값 갱신
        else:
            answer += num_max - num

    print(f"#{test_case} {answer}")

 

참고

• 난이도 : D2

 

역순으로 리스트 원소 조회하기

list[::-1]

 

• @[::-1]@
  • 슬라이싱을 사용하여 리스트의 요소를 추출하는데, @[start:stop:step]@ 형식의 슬라이싱 구문을 사용할 수 있다.
  • @start@
    • 슬라이스를 시작하는 인덱스를 지정한다.
    • 이 경우 비워져 있으므로 리스트의 시작부터 선택된다.
  • @stop@
    • 슬라이스를 끝내는 인덱스를 지정한다.
    • 이 경우 비워져 있으므로 리스트의 끝까지 선택된다.
  • @step@
    • 슬라이스의 간격을 지정한다.
    • 이 경우 @-1@로 설정되어 있으므로 리스트를 역순으로 추출한다.