BOJ 25414

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

 

코드

http://boj.kr/f3de6e6220654d93aaa53a55a98a0280

업솔빙

http://boj.kr/15a136f934dd42349cf2c778d88cc50f

 

난이도 : P1

 

Elapse Time : 실패

 

문제를 보고 #11858과 비슷하다는 느낌을 받았다. 이 문제에서는 구간을 남길 이유가 없기 때문에 결국 주어진 수열을 $K$개의 구간으로 쪼개는 문제가 된다. 그래서 #11858에서 사용했던 스택을 사용할 수 있는지 살펴보았는데 #11858에서는 최댓값만 관리하기 때문에 monotone stack으로 값을 관리하기 쉬웠지만 이 문제에서는 최댓값과 최솟값 모두를 관리해주어야 하기 때문에 스택으로 푸는 것은 무리가 있어 보였다. 그 후 최댓값과 최솟값 기준으로 나누어보려는 시도 등을 해봤지만 모두 실패했다.

 

문제를 푸는 데 실패하고 인터넷 검색으로 JusticeHui님의 풀이를 보았다. 어차피 $K$개의 숫자를 더하고 $K$개의 숫자를 빼기 때문에 그냥 더하는 $K$개의 숫자를 고르고 빼는 $K$개의 숫자를 골랐을 때 최댓값을 구해주면 된다는 것이 풀이의 핵심이었다. 여기서 구간이 겹치지 않기 때문에 특정 구간에서 더하는 숫자의 개수와 빼는 숫자의 개수의 차이가 1을 넘어가지 않도록 관리해주어야 한다. 이를 관리하기 위해서 $dp[0][i][j]$를 $1$부터 $j$까지 $i$개의 구간을 골랐을 때 최댓값으로 정의하고 $dp[1][i][j]$를 $1$부터 $j$까지 $i$개의 구간을 고르고 더하는 숫자 하나를 더 골랐을 때, $dp[2][i][j]$를 $1$부터 $j$까지 $i$개의 구간을 고르고 빼는 숫자 하나를 더 골랐을 때의 최댓값으로 각각 정의하면 $dp[1][i][j]=\mathrm{max}(dp[1][i][j-1],dp[0][i][j-1]+v[j])$, $dp[2][i][j]=\mathrm{max}(dp[1][i][j-1],dp[0][i][j-1]-v[j])$, $dp[0][i][j]=\mathrm{max}(dp[0][i][j-1],dp[1][i-1][j]-v[j],dp[2][i-1][j]+v[j])$라는 점화식을 세울 수 있고 이를 통해 풀었다. 생각보다 메모리와 시간 측면에서 다른 분들의 풀이와 큰 차이가 나길래 koosaga님의 코드를 참고해 업솔빙을 진행했다. 점화식을 보면 두 번째 인자는 직전 인자만 참고하므로 메모리를 줄일 수 있고 $dp[1][i][j]$, $dp[2][i][j]$ 의 점화식을 보면 굳이 모든 값을 저장할 필요 없이 $dp[0][i-1][j]$의 값만 가지고 최댓값으로 갱신만 해주면 된다는 것을 알게 되었다. 이를 통해 시간과 메모리를 획기적으로 줄일 수 있었다.