06vfsunny   9달 전

제가 풀려고 했던 방법이
어떤 k+1개 방이 있는 큐가 있고 i번째 시행에서 해당 큐의 j번째 방은 i번째 수를 포함해서 연속 j개의 값을 선택하는 방법 중 최대값으로 했습니다.

그니까 0번째 방은 i번째 시행에서 i번째 수가 선택되지 않는 경우의 수 중 가장 큰 누적값을 가진 방인거죠. 예를 들어 위 문제의 예에서 5, 2 [1, 2, 3, 4, 5]이 것에서

0번째 시행에서는 큐가

[0, 1](0번째 방은 1이 선택되지 않는 누적값, 1번째 방은 1이 선택되는 누적값)

그 다음은

[1, 2, 3] (0번째 방은 i-1번째 방 최대값 1, 1번째 방은 0+2, 2번째 방은 1+2)

[3, 4, 5]

[5, 7, 8]

[8, 10, 12] 이런 방식으로 큐가 돌아갑니다. 한마디로 오른쪽으로 시프팅하며 가장 오른쪽에 있던 수를 제외하고는 전부 i번째 수가 더해지는 규칙이므로 이를 O(1)에 해결하기 위해 오른쪽에 있던 수에만 E_i를 빼고 나중에 total 누적값을 전체에 더하는 방식으로 최적값을 구했습니다. 이때 만약 가장 오른쪽에 있던 수에서 E_i를 뺐음에도 가장 왼쪽에 있던 수보다 크다면 최적해를 찾는 것에 방해되고 쓸데없는 값이 큐에 존재하기에 이 큐를 덱으로 바꿔서 deq[가장 오른쪽]-E_i>=deq[가장 왼쪽]일 시 계속 pop하게 해서 덱 최적화를 했습니다. 또한 이렇게 할 시 덱의 크기가 K+1로 고정되지 않을 수 있음으로 마지막으로 가장 오른쪽에서 가장 왼쪽으로 시프팅했을 시점의 i를 함께 덱 요소에 넣어 만약 해당 i가 현재의 i와의 차가 k보다 클 경우 바로 다시 시프팅을 하게 만들었습니다. 이런 방식으로 만들었는데 혹시 논리가 맞지 않거나 제가 실수한 지점이 있을까요? 반례도 함께 주시면 감사하겠습니다.

틀리는 것은 62프로 지점에서 틀립니다.

davidjh315   8달 전

짱 멋있는풀이네요 참고할게요!

댓글을 작성하려면 로그인해야 합니다.