[실버 II] 4096번. 수익

 문제 

https://www.acmicpc.net/problem/4097

4097번: 수익

 사용 언어 

Python3

 풀이 과정 

간단한 DP 문제이다. 점화식이 쉬운 건 그래도 풀 수 있는 것 같다.

그런데 다른 DP 문제에서 부분합을 구하기 위해 for문을 사용했던 게 생각나서 dp 리스트를 따로 만들고 지금까지의 합과 새로운 값을 더한 값을 비교해 저장하려 했는데 이건 이중 for문을 사용할 필요도, dp 리스트를 따로 만들 필요도 없었다.

 

그래서 생각보다 간단하게 풀린 맞았습니다!!

근데 생각보다 시간은 많이 나온 것 같아 다른 사람 코드를 찾아보았다.

 

 제출 답안 

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    while True:
        N = int(input())
        if N == 0:
            break
        profits = [int(input()) for _ in range(N)]
        for i in range(1, N):
            if profits[i] < profits[i] + profits[i-1]:
                profits[i] = profits[i] + profits[i-1]

        print(max(profits))

 

 다른 사람 코드 

1. 나보다 공간복잡도, 시간복잡도가 모두 월등히 높은 (현재까지) 1등의 코드이다.

import sys
input = sys.stdin.readline


def main():
    while 1:
        N = int(input())
        if N == 0:
            break   # 테스트케이스 종료

        arr = [int(input()) for _ in range(N)]
        print(maxProfit(N, arr))


def maxProfit(N, arr):
    sum = [0 for _ in range(N)]
    sum[0] = arr[0]         # 0번째까지의 최대 합은 arr[0] 그대로
    for i in range(1, N):
        if sum[i - 1] > 0:  # 이전까지의 합이 양수면 sum[i - 1] + arr[i]가 최대
            sum[i] = sum[i - 1] + arr[i]
        else:               # 이전까지의 합이 음수면 arr[i]가 최대
            sum[i] = arr[i]

    return max(sum)


main()

➡ 사실 이게 정확히 처음에 내가 구현하고 싶었던 방법이다. maximum이라는 함수를 따로 만들었다가 profits라는 리스트로 바로 쓰려고 지웠는데 sum(dp 메모이제이션용) 리스트를 따로 만들어서 풀어도 간단했던 것 같다.

 

어쨌든 로직은 비슷한데 이게 시간복잡도가 훨씬 적은 이유는 모르겠고... 공간복잡도가 적은 이유는 profits를 덮어쓰면서 더 비효율적으로 사용된 것 같다. 덮어쓰면 새로운 리스트를 생성하는 것보다 좋아야 하는 것 아닌가? 어렵다...