[ BOJ / 파이썬 ] 1912 연속합

으 .. 아직 DP연습량이 안 쌓인건 알았지만, 이렇게 DP아이디어가 아예 안 떠오를 줄은 몰랐다.

심지어 1시간 지나고 포기한 이제야 아 이게 DP문제라서 풀려고 선택한 문제지.. 라고 풀이유형이 이제 생각난다.

진작에 생각 났어도 몰랐겠지만.. ㅎ 계속 경험치 쌓자.

 

1차 아이디어.

쭉 가다가 감소 나오면 일단 끊는다. 그리고 이전에 끊긴 양수값과 비교해 큰 값을 남겨놓는다. => 문제 로직에 안 맞음.

 

2차 아이디어.

나름 참신하게 한다고 했는데 그냥 1차 아이디어를 뒤에서부터 접근하는 식이 되었다. 각 값에 이어지는 최댓값을 따로 테이블에 적어줄 뿐이었다. 메모제이션스럽게 한다고 흉내낸 생각인데 스스로 반례 발견해서 포기. 애초에 잘못된 접근인걸지도.

 

3차 아이디어. 

일단 전체 데이터 쭉 훑으면서 양수 범위, 음수 범위 단위로 끊는다. 그래서 값을 한차례 줄여나가려 했다. 이건 끝까지 가보려 했는데 구현 실패. 로직이 잘못되었더라고 내가 생각한 아이디어는 끝까지 풀어내야한다고 생각하는데, 계획한 시간이 이미 지나서 일단 마무리 지었다.

---

 

다른 분들 풀이 보고 풀이해보려 한다. 아마 비슷한 문제가 많아 다음에 다시 연습 가능할 것 같다는 생각이 들어서이다. 절대 자기합리화 x 많이 생각해 본 문제이다.

 

  -> 다른 분들 풀이 봤는데 꽤 허탈하다.. 구현이나 아이디어가 되게 쉬워서.. DP를 활용한다는 사실을 더 잘 떠올리면 풀 수 있었을 것 같고, 특히 해당 파트에 덜 쫄아 있었으면 풀 수 있을 것 같다는 생각이 들었다. 그런데 틀린 건 틀린 거고, 원래 DP는 구현 자체는 쉽지만 아이디어 구상이 어려운 거니까 아.. 할 수 있었겠다의 아쉬움은 그냥 오만인 것 같다. 면밀히 정리해보자.

 

1. DP테이블 정의

: 해당값까지 이어져 오는 최대값

 

2. DP점화식 정의

: 이전 DP값은 이전 숫자값의 최대합이다.

: 여기에 내 숫자를 더해서 더 커지면 더 하면 최대값이 되는거니까 더해주고, 아니면 더하지 않는다. 이게 내 첫 풀이였다.

: 여기서 하나 더 따져야 or 더 세밀하게 생각해야 정답일 수 있다. 이전 최대값이 음수일 때가 포인트이다.

: DP를 따지는거니까 nums가 음수냐는 중요하지 않다. 나는 nums가 음수냐를 기준으로 해서 꼬인거다.

: 현재까지의 '합'이 주인공! 우리 목표!

 

: 그래서, 이전까지의 합이 음수면 현재 값이 양수건 음수건 포함 안 하고 나부터 새로 시작하는 값으로 넣어준다.

: 이전까지의 값이 양수면, 내가 양수건 음수건 같이 합쳐 넣어준다.

 

3. 초기값은 이게 1차원 배열이므로, 순서대로 쭉쭉 가는거라서 단순하게 첫 번째 값을 dp[0]으로 초기화하면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())

nums = list(map(int, input().split()))
dp = [0] * len(nums)

dp[0] = nums[0]

for i in range(1, len(nums)):
  if dp[i-1] < 0:
    dp[i] = nums[i]
  else:
    dp[i] = dp[i-1] + nums[i]
  
print(max(dp))

 

: 여기서 한 번 더 짚을 것.

: dp 첫 값 초기화 안 하는 실수 해서 제출에서 또 틀렸다. ㅠ 마지막으로 항상 확인하고 제출할 것.

 

+ 이 풀이를 왜 안 하려고 처음에 했냐면, 마지막에 최댓값 구할 때 전체 배열을 한 번 더 돌면, 너무 시간이 많이 소요되나라는 의심 때문이었다. 근데 DP배열이니까 그냥 max()함수를 사용해서 간단하게 구할 수 있는 거였다. 사실 유형에 익숙하면 이럴 일 없었을 것 같다. 계속 많이 풀자.