[boj] 2228_구간 나누기_python

문제링크

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

2228번: 구간 나누기

---

문제설명

 

문제

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

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

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

 

입력

1.  두 정수 N, M. N은 배열을 이루는 수, M은 구간의 수

2~N+1 :  배열을 이루는 수들이 차례로 주어진다

 

출력

1.  구간에 속한 수들의 총 합의 최댓값

 

제한

• 배열에 저장되는 수의 범위  : [ -32768, 32767 ]구간에 속하는 정수
• 각 구간은 한 개 이상의 연속된 수들로 이루어진다.
• 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다.
• 정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다.

---

문제풀이

 

---

 

# 시간 복잡도 : O(N * M) or O(N * ⌈(N/2)⌉ ) ( range_split 함수)
# 공간 복잡도 : O(N²)
# 풀이 시간 : 6시간
# 참고 링크 https://loosie.tistory.com/260
import sys
input = sys.stdin.readline
N, M = map(int, input().split()) # N : 수의 개수, M : 구간의 개수
res = [0] # 초기 리스트
for i in range(1, N+1): res.append(int(input()) + res[i-1]) # 누적합의 결과 저장
DP = [[0 for _ in range(M+1)] for _ in range(N+1)] # DP[ 수의 개수 ][ 구간의 수 ]
visited = [[False for _ in range(M+1)] for _ in range(N+1)]
# r : 최대 수, s : 남은 구간의 개수
# Top-Down 방식으로 구현된다.
def range_split(r, s):
    if s == 0: return 0
    if r <= 0: return -3276800 #
    if visited[r][s]: return DP[r][s]
    visited[r][s] = True
    DP[r][s] = range_split(r-1,s)
    for i in range(r, 0, -1):
		# 기존 값 vs 구간이 인접하지 않게 하기 위한 i-2 + 누적합의 차
        DP[r][s] = max(DP[r][s], range_split(i-2, s-1) + res[r]-res[i-1])
    return DP[r][s]
print(range_split(N,M))

 

---

참고 레퍼런스

1. https://loosie.tistory.com/260

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