Baekjoon13398 - 연속합 2 (Python)

백준 사이트 13398 - 연속합 2 문제입니다.

이 글을 보시기 전에 문제를 풀기 위해 충분한 생각을 하셨나요? 답을 안 보고 푸는게 최대한 고민하는게 가장 중요하다고 생각합니다.!!

☑️ 1. 문제

https://www.acmicpc.net/problem/13398

---

☑️ 2. Input , Output

---

☑️ 3. 분류 및 난이도

코딩테스트 준비-기초 : 브루트포스 - 다이나믹프로그래밍 문제입니다.

---

☑️ 4. 생각한 것들

• 요소 하나를 삭제할 수 있기 때문에 삭제했을때 경우, 삭제를 하지 않았을때 경우를 생각해야합니다.
• 삭제 안 했을경우는 순차적으로 합한 경우 vs 현재 인덱스의 값을 비교해나가면서 해결하면 됩니다.
• 삭제의 경우는 딱 한 번만 삭제가 가능하므로, 전의 인덱스까지를 순차적으로 합한경우(삭제의 경우입니다.) vs 이미 삭제한 경우의 순차합을 비교해야합니다.
• 그래서 총 2개의 메모제이션 자료구조를 사용하였습니다.

---

5. code

from sys import stdin


def solution() -> int:
    def init():
        num = int(stdin.readline())
        data_list = list(map(int, stdin.readline().split()))
        return num, data_list

    n, input_list = init()
    dp = [0] * n
    delete_dp = [0] * n
    dp[0] = delete_dp[0] = input_list[0]
    max_num = input_list[0]

    for i in range(1, n):
        # 삭제의 경우
        delete_dp[i] = max(delete_dp[i - 1] + input_list[i], dp[i - 1])
        # 순차합과 본인 인덱스 값을 비교
        dp[i] = max(dp[i - 1] + input_list[i], input_list[i])
        max_num = max(max_num, dp[i], delete_dp[i])
    return max_num


result = solution()
print(result)

---

6. 후기

c++로 작성이 필요하거나 도움이 필요하시면 댓글을 작성해주세요.!! 기록용이라 설명이 자세하지 않습니다.