[BOJ 25188] 백준 25188번 - 1, 3, 모 나누기

		2022 서강대학교 청정수컵 풀이
A		[BOJ 25175] 두~~부 두부 두부
B		[BOJ 25176] 청정수열 (Easy)
C		[BOJ 25177] 서강의 역사를 찾아서
D		[BOJ 25178] 두라무리 휴지
E		[BOJ 25179] 배스킨라빈스~N~귀엽고~깜찍하게~
F		[BOJ 25180] 썸 팰린드롬
G		[BOJ 25181] Swap the elements
H		[BOJ 25182] 청정수열 (Hard)
I		[BOJ 25183] 인생은 한 방
J		[BOJ 25184] 동가수열 구하기
K		[BOJ 25185] 카드 뽑기
L		[BOJ 25186] INFP 두람
M		[BOJ 25187] 고인물이 싫어요
N		[BOJ 25188] 1, 3, 모 나누기

1. 문제

$25188$. 1, 3, 모 나누기 (2022 서강대학교 청정수컵 N번)

백준 25188번 - 1, 3, 모 나누기 (https://www.acmicpc.net/problem/25188)

2. 풀이

좀 더 쉬운 풀이를 원하면, 공식 해설 pdf를 참고하는 것을 추천한다.

연속된 원소의 합의 최댓값을 찾는 문제로 유형이 비슷해서 BOJ 25049번 풀이의 방법을 응용하였다. 따라서, 이 글의 내용을 기반으로 설명하고자 한다.

위의 $25049$번 문제는 두 구역으로 나누기 때문에 기준점을 하나만 설정하면 된다. 그러나, 이 문제는 총 $6$개의 구간이 있다. 구간이 원소를 포함하지 않을 수도 있으므로 $2,4,6$번 구간을 신경쓰지 않는다고 가정하면, $1,3,5$번 총 세 구간이 있다고 볼 수 있다. 따라서 두 개의 기준점이 필요하다.

그런데, $1$번 구간은 원소가 $0$개가 아닌 이상 무조건 $1$번 index에서 시작해야 한다. 따라서 $1$번 구간은 dp를 사용해서 부분구간의 최대합을 구하는 것이 아니라, $1$번 index에서 오른쪽으로의 누적합을 사용해야 한다.

$1$번 구간의 오른쪽 끝점이 정해짐에 따라서, $25049$번 문제의 방법대로 나머지 구간을 두 구간으로 나누어 왼쪽 max_dp, 오른쪽 max_dp의 합을 구하면 된다. 여기에 $1$번 구간의 누적합을 더하면, $1,3,5$번 구간의 최대합이 된다.

모든 $1$번 구간의 오른쪽 끝점에 대해 도출된 최대합의 최댓값을 찾으면, 정답을 구할 수 있다.

3. 채점 결과

4. 회고

인덱싱이 상당히 까다로워서 실수하기 쉽다. $25049$번 문제와 마찬가지로 최솟값을 $0$으로 잡아주어야 하는 부분들도 존재해서 더 복잡하다.

5. 코드