백준 2228: 구간 나누기 (Python)

접근

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

2228번: 구간 나누기

점화식을 생각해내기가 어려웠고, 구글을 통해 점화식에 대한 힌트를 얻어 문제를 해결할 수 있었다.

n번째 원소까지의 m개 구간합을 구하고자 할 때, max(n-2번째 원소까지의 m-1개 최대 구간합, n-1번째 원소까지의 m개 최대 구간합) + 현재값의 점화식을 통해 문제를 해결할 수 있다.

1. n-2번째 원소까지 m-1개의 구간으로 나누고 n번째 원소를 m번째 구간으로 하여 구한 합과,
2. n-1번째 원소까지 m개의 구간으로 나누고 n번째 원소를 m번째 구간에 포함하여 구한 합을 비교하는 것이다.

이 문제를 해결하기 위해 i번째 수를 포함하는 j개 최대 구간합을 concluded[i][j]에 저장하고, i번째 수를 포함하지 않는 j개 최대 구간합을 notConcluded[i][j]에 저장하였다. 이 두 matrix의 마지막 값 중 큰 값을 출력하여 문제를 해결할 수 있다.

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
concluded = [[0] + [float("-inf")] * M for _ in range(N + 1)]
notConcluded = [[0] + [float("-inf")] * M for _ in range(N + 1)]

for i in range(1, N + 1):
    num = int(input())
    for j in range(1, M + 1):
        notConcluded[i][j] = max(concluded[i - 1][j], notConcluded[i - 1][j])
        concluded[i][j] = max(concluded[i - 1][j], notConcluded[i - 1][j - 1]) + num

print(max(concluded[N][M], notConcluded[N][M]))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!