1912

백준 1912 풀이 (연속합, 다이나믹 프로그래밍)

이거 진짜 쉬운줄 알았는데 DP로 풀어야해서 헤맸던 문제이다. 처음에는 값을 누적시켜서 DP느낌으로 풀었는데 시간 복잡도가 n제곱이라 자꾸 시간초과가 났다. 그래서 내가 푼 방식이 잘못되었다는 것을 깨닫고 한참을 헤매었다. n = int(input()) nl = list(map(int, input().split())) dp = [0 for i in range(n)] big = -1000 for size in range(n): for i in range(n-size): dp[i] += nl[i+size] tmp = max(dp) if tmp > big: big = tmp print(dp) print(big) 그래서 고친게 다음과 같다. n = int(input()) nl = list(map(int, inp..