이 때, 구간에 속한 수들의 총합을 구하는 문제이다.
dp다. 분명 약 두 달전에 푼 것으로 돼있는데... 딱 떠오르지가 않는다.
한 번 생각을 해보자.
d[n][m] = n번째 수부터 구간으로 선택할지 말지 결정해야 하고 만들어야 하는 구간은 m개일 때, n번째 수부터 시작해서 m개의 구간에 속한 수의 총합의 최대값
d[n][m]= MAX( d[n+1][m], a[n]+d[n+1][m], a[n]+d[n+2][m-1]) 인 것 같다.
2. a[n]+d[n+1][m]은 a[n]을 선택했지만 아직 하나의 구간이 끝나지 않은 경우이다.
3. a[n]+d[n+2][m-1]은 a[n]을 선택했고, a[n]에서 하나의 구간이 끝난 경우이다. 주의해야할 점은 구간끼리 붙어있으면 안되기 때문에 n+2번째부터 봐야한다.
이제 구현에 들어간다.
m개 이하가 아닌 m개의 구간이 모두 있어야 한다는 조건 처리해주는 것도 주의해야할 점이다.
제출했는데 WA를 받아서 여러 테스트 케이스도 해보고 고민하던 차에... 코드를 보는데...아... 감사합니다... 생각이 떠올랐다.
보통 dp를 할 때, 배열을 -1로 초기화하는데, 이 문제는 dp배열이 총합의 최대값을 나타내는데, 총합의 최대값은 음수가 될 수도 있다. 즉 -1이 될 수도 있다... 이것은 따로 check배열을 놓고 해야한다. 고쳐서 다시 제출해야겠다.
근데 또 WA를 받아서 내가 원래 풀었던 AC코드랑 비교하는 중이다. 예전에는 내가 미리 부분합을 구해놓고 부분합을 이용해서 풀었던 것으로 보인다. 일단 랜덤으로 데이터를 생성해서 비교해보겠다.
비교해 봤는데... 1. d[n+1][m]은 a[n]을 선택하지 않았을 때의 경우라 생각했는데...잘못됐다... d[n-1][m]에서 a[n-1]을 선택하고, d[n][m]을 호출했고, d[n+1][m]을 하려고 한다면 a[n]은 선택하지 않은 것이므로 그룹이 끊긴게 되는데, d[n+1][m]으로.. m이 그대로이다. 중간에 선택을 안하는 경우는 그룹이 끊겨서 결국 하나의 그룹을 쓴 것으로 되므로 m을 1줄여야 되는데 그 것이 안되서 틀린 것으로 보인다. 이것을 보완하려면 그룹이 이어지는 것인지 아닌지를 체크해줄 것이 필요하다. parameter를 하나 더 써서 해봐야겠다.
처음에는 parameter만 추가하려고 했는데, 이어지는지 아닌지에 따라 뒤의 값이 바뀔 수 밖에 없으므로 memoization이 제대로 되려면 d[n][m][con]이렇게 이어지는지 아닌지도 추가해줘야 한다. 결국 AC를 받았다.
위의 틀린 이유를 찾아낼 수 있게 해준 test case
n = 12, m = 1
27, 4, -17, -4, -3, 13, 10, 7, 7, 4, -6, -14
이제 예전에 풀었던 방법으로도 풀어보고 다시 정리해 봐야겠다.
배열의 부분합을 입력받으면서 구해놓고,
d[n][m] = n번째 수부터 보는데, 만들어야 하는 구간은 m개일 경우 m개의 구간에 속한 수들의 총합의 최대값
d[idx][cnt] = d[idx+1][cnt] // a[idx]를 선택하지 않는 경우
d[idx][cnt] = MAX(d[idx][cnt], d[idx+k+1][cnt-1]+psum[idx-1+k]-psum[idx-1]) (k는 1에서 idx+k-1 <= n-(cnt-1)*2 일 때까지) //a[idx]를 포함해서 k개 연속으로 선택하는 경우
->위의 두 가지 방법으로 다시 풀어봤는데 아래 방법에서
선택하지 않는 경우와 k개 연속으로 한 그룹으로 선택하는 경우에서.. k개 연속으로 선택하는 것으로 구현하려고 하면 구현이 좀 까다롭다... 복잡해진다. 실수할 확률이 높아진다.
오늘 다시해보니 이렇게 하는게 훨씬 구현하기 편하다.
xth부터 i까지 선택하는 것으로 하는 것이 훨씬 구현이 편하다! 결국은 똑같은 뜻이지만 굳이 k개를 선택한다는 것을 곧이곧대로 구현하기보다 ~까지 선택하는 식으로 구현하는 것이 훨씬 낫다!
댓글 없음:
댓글 쓰기