반응형
문제: https://www.acmicpc.net/problem/13398
13398번: 연속합 2
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
풀이:
1912번 연속합 문제에서 수를 하나 제거하는 경우가 추가된 문제이다.
수를 제거한 경우와 제거하지 않은 경우를 나누어 dp 배열을 생성하고 큰 수를 비교하면서 저장해 나가면 된다.
항상 느끼는 거지만 다이나믹 프로그래밍 문제는 코드는 정말 간단하지만 문제의 규칙, 점화식을 생각해내는 과정이
너무 어렵다.
정답:
import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dp = [[0] * n for _ in range(2)] # 수를 한 번 제거한 경우와 제거하지 않은 경우를 나눔 # 제거할 횟수가 남아있는 배열은 dp[1]에, 제거할 횟수가 남아 있지 않은 배열은 dp[0]에 저장 dp[0][0] = arr[0] dp[1][0] = arr[0] for i in range(1, n): # 그럼 dp[0][i]는 본인을 제거한 나머지의 합 dp[1][i-1과] 이전에 제거된 배열과 본인의 합 중 더 큰 값이 dp[0][i]이 된다. dp[0][i] = max(dp[1][i-1], dp[0][i-1] + arr[i]) # dp[1][i]는 본인 혼자만의 합과 이전의 합 중 더 최대인 값을 고르면 된다. dp[1][i] = max(dp[1][i-1]+arr[i], arr[i]) result = -10001 for i in range(2): for j in range(n): if dp[i][j] > result: result = dp[i][j] print(result)
반응형
'Python 코딩테스트' 카테고리의 다른 글
DP(다이나믹 프로그래밍): 백준 15988 파이썬 1,2,3 더하기 3 (0) | 2022.10.13 |
---|---|
[프로그래머스] 기능개발 파이썬 (1) | 2022.10.11 |
DP: 백준 11052 파이썬 카드 구매하기 (1) | 2022.10.06 |
[백준] 2178 미로 탐색 파이썬 (0) | 2022.09.28 |
[백준] 2606 바이러스 파이썬 DFS/BFS (0) | 2022.09.27 |