[백준 2228번] 구간나누기 (python)

문제

N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.

1. 각 구간은 한 개 이상의 연속된 수들로 이루어진다.
2. 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다.
3. 정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다.

N개의 수들이 주어졌을 때, 답을 구하는 프로그램을 작성하시오.

 

기록

(dp 12일차) 여름휴가 갖고 새롭게 시작! 부터 너무 어려웠다. 

 

이번 문제는 특정 원소까지의 n개 구간합을 구하고자할 때, max(앞의 원소를 제외한 n-1개의 최대 구간합, 앞의 원소를 포함한 n개의 최대 구간합)+현재값을 적용해서 구했다. 아래 그림으로 표현.

구현을 위해 배열 두 개 만들어서 (1) notcon[i][j]는 i번째 수를 포함하지 않는 j개 구간합 중 최댓값, (2) con[i][j]에는 i번째 수를 포함하는 j개 구간합 중 최댓값을 저장했다. 이 두 배열을 이용하여 위 그림 구현해서 풀었다!

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
con = [[0]+[-1e9]*m for i in range(n+1)]
notcon = [[0]+[-1e9]*m for i in range(n+1)]

for i in range(1, n+1):
    num = int(input())
    for j in range(1, min(m, (i+1)//2)+1):
        notcon[i][j]=max(con[i-1][j], notcon[i-1][j])
        con[i][j]=max(con[i-1][j], notcon[i-1][j-1])+num
print(max(con[n][m], notcon[n][m]))

1. i번째 수를 포함하는 j개 구간합 중 최댓값을 저장할 con[i][j], i번째 수를 포함하지 않는 j개 구간합 중 최댓값을 저장할notcon[i][j] 생성

2. notcon 배열에는 max(i-1번째 수를 포함한 j개 구간합, i-1번째 수를 포함하지 않은 j개 구간합)해서 저장한다. 한마디로 현재 원소 앞까지(포함하지 않는다는 의미) j개 구간합 최댓값 저장하는 것.

3. con 배열에는 max(i-1번째 수를 포함한 j개 구간합, i-1번째 수를 포함하지 않은 j-1개 구간합)해서 저장한다. 위의 그림에서 설명했듯이 현재 원소를 포함한 구간합의 최댓값 저장하는 것.

4. 마지막 원소를 포함한 구간 최댓값이랑 마지막 원소를 포함하지 않은 구간 최댓값 비교해서 더 큰 값 출력하면 끝~!