나만의 개발블로그

풀이 초기 생각한 방법은 아래 두 번째 코드처럼 각 위치에서 슬라이싱한 값 까지의 합 중 가장 큰 값을 출력하고자 했지만 2% 에서 시간 초과 발생 그래서 dp를 활용한 문제 해결을 위해 현재 위치 전까지의 가장 큰 값(이전 dp값) + 현재 위치의 배열 값과 현재 배열의 값 중 큰 값을 현재 dp의 값에 저장하여 최종적으로 가장 큰 값을 출력하여 해결! 정답 코드 import sys input = sys.stdin.readline n = int(input()) li = list(map(int,input().rstrip('\n').split())) dp = [0]*n dp[0] = li[0] for i in range(1,n): dp[i] = max(dp[i-1]+li[i], li[i]) print(ma..

DP를 계속 풀면서 느낀 점으로 더 큰 값을 누적하며 dp를 쌓아 올려갈 때 비교해야 하는 대상 선정이 가장 중요한 것 같다. 처음 해당 문제를 접했을 때 li[i]+dp[i-1] 과 비교할 대상으로 dp[i-1]를 선택했는데 이유는 지금까지 누적한 값의 가장 큰 값 + 현재 값과 현재 값을 더하지 않은 누적 값을 비교해야 하는 거 아닐까? 라는 생각으로 접근했을 때 접근 방법에 대한 문제가 있다고 판단. 그래서 지금까지 누적한 값 + 현재 값과 현재 값부터 다시 시작하기 위한 현재 값만을 비교 후 더 큰 값을 현재 dp 값에 저장하여 문제를 해결 위의 로직을 기반으로 계속해서 각각의 위치에서 시작했을 때 가장 큰 값과 비교가 가능한게 아닐까라는 생각을 함. import sys input = sys.st..