-
[백준 1912번] 연속합Coding Test/백준 2021. 2. 14. 00:31
# 문제
내 풀이 - 문제 풀이 실패, 수정 답안
n = int(input()) nums = [-1001] # 인덱스를 맞추기 위해 가장 작은 수를 하나 삽입 nums = nums + list(map(int, input().split())) # 점화식을 기록하는 테이블을 만들고 초기화 n_sum = [-1001] * 100001 n_sum[1] = nums[1] # 왼쪽부터 차례로 합을 더해나가면서 새로운 수와 비교 for i in range(2, n + 1): n_sum[i] = max(n_sum[i - 1] + nums[i], nums[i]) # 결과 출력 print(max(n_sum))
생각해볼 점
정석적인 DP 테이블만 생각했는데, 약간 변형하여 점화식을 기록해나가는 방법도 있음을 알았다. 생각을 유연하게 가질 수 있어야 할텐데... 다이나믹 프로그래밍이 참 쉽지 않은 것 같다.
'Coding Test > 백준' 카테고리의 다른 글
[백준 2798번] 블랙잭 (0) 2021.02.14 [백준 12865번] 평범한 배낭 (0) 2021.02.14 [백준 9251번] LCS (0) 2021.02.08 [백준 2565번] 전깃줄 (0) 2021.02.07 [백준 11054번] 가장 긴 바이토닉 부분 수열 (0) 2021.02.06