백준 13398번 파이썬 - 연속합2

 

13398번: 연속합 2

관련된 문제로 연속합 문제가 있는데, 이번에는 연속합2 이다.

dp는 역시, 이전의 값을 참조해서 답을 찾아나가는 과정! 경우의 수를 잘 나누는 것이 진짜 중요하다. => 점화식 빠르게 찾는 지름길*

10만이 입력이라서, 2차원 배열은 포기해야겠네 생각했었다. 하지만 그렇다고 해서 2차원 배열을 바로 포기해서는 안된다. 내가 어떻게 써먹는지에 따라 시간적 효율성은 달라지기 때문.

풀이

이 문제는 두 가지의 경우의 수로 나눌 수 있다. 이 힌트만으로도 문제 풀이가 금방 떠오를 수 있다.

1. dp[0][i] : 특정 원소를 제거 하지 않은 경우의 연속합. ( i 까지 원소들 중 최대 연속합)
2. dp[1][i] : 특정 원소 하나를 제거한 경우의 연속합. ( i 까지 원소들 중 하나를 제거한 연속합) => 문제 조건에 하나 제거 가능.

코드

n = int(input())
arr = list(map(int,input().split()))

dp = [[0] * n for _ in range(2)]
# 최소한 한 개는 선택해야함.
dp[0][0] = arr[0]
ans = -1001

if n > 1:
    for i in range(1, n):
        # 0 -> 원소를 제거하지 않는 경우. 제거가 없는 연속 합 중 최대합.
        # 1 -> i까지 원소들 중 하나 제거하는 경우 중 최대합
        dp[0][i] = max(arr[i], dp[0][i - 1] + arr[i])
        # i - 1번째 까지 원소들 중 하나 제거한 경우들, i 번째 원소를 제거 한 경우 최대 연속합.
        dp[1][i] = max(arr[i] + dp[1][i - 1], dp[0][i - 1])
        ans = max(ans, dp[0][i], dp[1][i])
    print(ans)
else:
    print(dp[0][0])

n == 1 인 경우는 최소한 한 개는 선택해야 하기 때문에 첫 번째 원소를 출력하면 된다.

느낀 점

dp는 점화식을 얼마나 잘 생각해내느냐 이다.

경우의 수를 어떻게 나눌 지에 대해서 생각하자.

2차원 배열 또는 1차원 배열을 이용할 생각을 하자. 문제 풀이 방법은 여러가지 이니, 또 일단 문제는 풀고 봐야하니까 도전하자.

문제에 조금의 힌트는 있다. 이 문제에서는 제거한 경우의 답, 제거하지 않은 경우의 답을 일부러 알려줌.

모두가 양수인 경우일 때는 제거하지 않는 경우로 답을 정할 수 있다.

음수에 너무 초점을 맞춰서 경우의 수를 나누는데 복잡하게 생각한 것 같다.

 

이 문제는 시간이 조금 지나고 다시 풀어봐야 겠다.

 

참고자료

[백준 13398] 연속합 2 (Python)