백준 1912 연속합 (파이썬)


1912 연속합 문제 바로가기

접근방식

  • 11053 가장 긴 증가하는 부분 수열의 알고리즘 형태를 조금 바꾸어 풀었다.
  • 전체 리스트를 돌면서 연속합+자기자신 더 나은지 자기자신만 사용하는 것이 좋은지 판단하고 싶었다.
  • 따라서 판단에 따라 dp에 여태까지의 연속합+자기자신 혹은 자기 자신만 더하도록 했다.
  • 전체 리스트를 돌며 dp[현재 인덱스-1]값이 dp[현재 인덱스]보다 크다면 연속합을 선택하고 자기자신을 더한다.


파이썬 코드

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

dp=[0 for i in range(n)]

for i in range(n):
    if dp[i] < dp[i-1]:
        dp[i] = dp[i-1]
    dp[i] = dp[i] + arr[i]

print(max(dp))

기록

  • 재귀부터는 구글링을 통해 푼 문제가 많았는데 이 문제는 처음으로 검색없이 스스로 푼 문제이다. 알고리즘 수업을 수강했음에도 불구하고 코테용 알고리즘 문제 풀이는 아직 시작하는 과정이니 구글링은 어쩔 수 없어! 라고 생각하다가도 이래도 되는건지 공부가 제대로 되고있는건지 스스로 의문이 많이 들었다. 아마 이 문제는 나의 실력이 아주 조금씩이라도 나아지고 있다는 좋은 징조가 아닐까?!





© 2020.09. by 다로

Powered by theorydb