[백준] 2228번: 구간 나누기 - python

문제 출처

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

2228번: 구간 나누기

 

 

 

 

 

---

풀이 및 코드

 

해당 문제는 대표적인 dp문제로 solved.ac에서 골드 3으로 랭크되어 있다.

 

필자는 dp[i][j]에 0~i 까지 j개의 구간을 나누었을 때의 최대값을 저장해 주었다. 숫자를 추가해가며(i를 증가시켜가며) dp[n][m]을 구했다. 이때, 총 3가지 상황으로 분류할 수 있다. 

 

1) i번째 요소를 구간에 포함시키지 않느다.

2) i번째 요소를 구간에 포함시키되, 기존의 구간에 덧붙인다.

3) i번째 요소를 구간에 포함시키되, 새로 구간을 생성한다. 

 

이 세 가지를 모두 고려해주면 된다.

 

 

필자는 두 개의 어레이를 구성해서 문제를 해결했다. i번째 요소를 구간에 포함시킨 경우와, 포함시키지 않은 경우 두가지 이다.

# 다음 숫자를 구간에 포함시킨 경우와 제외시킨 경우, [i][j] = 0~i까지 j 구간을 설정했을 때 최대값 저장
contain = [[-float("inf") for _ in range(m+1)] for _ in range(n)]
notContain = [[-float("inf") for _ in range(m+1)] for _ in range(n)]

 

 

이렇게 두 가지 어레이로 구상했다면, 점화식은 다음과 같다. 

contain[i][j] = max(contain[i-1][j], notContain[i-1][j-1]) + arr[i]
notContain[i][j] = max(contain[i-1][j], notContain[i-1][j])

 

contain[i][j] = max(contain[i-1][j], notContain[i-1][j-1]) + arr[i] 

i번째 요소를 구간에 포함시킨 경우인 해당 점화식로 앞서 말한 2, 3번 문제를 해결했고

 

notContain[i][j] = max(contain[i-1][j], notContain[i-1][j])

i번째 요소를 구간에서 제외시킨 경우인 해당 점화식으로 1번 문제를 해결했다.