특별한 서빙

27896번: 특별한 서빙

문제 설명

$N$명의 학생들이 순서대로 $x_i$만큼의 값을 뺄지 아니면 더할지를 정하는데 해당 불만도의 총 합이 $M$이 넘어서는 안된다. 이때 $M$이하로 만들기 위해 최소 몇 번 빼야하는가

잡담

문제 이해가 조금 힘들었다. 길이는 짧은 데 이해가 안됐다.

풀이

이유는 모르겠지만 처음부터 그냥 그리디라고 생각했다. 그래서 생각을 구체화 시켰다.

• $N$명의 불만도를 순차적으로 더하고 pq에 insert한다. ($O(N)$)
  • 이때 $M$보다 불만도 값이 크다면 pq에서 가장 큰 값을 뽑아 2*$x_{pq}$ 값을 불만도에서 뺀다. $O(\log N)$
    • 여러번 pq에서 값을 빼야하는 상황이 있을까? → 없다.
      • $sum_{i}=sum_{i-1}+x_i$
      • if $sum_{i-1}+x_i >= M$
        • $sum_{i}=sum_{i} - 2 \times max(x_{0...i})$
        • $x_i \leq max(x_{0...i})$
        • so $sum_{i}<M$

그래서 $O(N\log N)$이다.

다른 방식

다른 사람들한테 풀어보라고 했더니 2가지 방법을 얘기했다.

1. combination
   조합은 왜 안될까? 코드를 보지 못해서 정확한 접근은 못봤지만 조합이라는 키워드를 봤을 때 풀이는 최소 개수를 이항 계수로 두고 문제를 푸는 방법이다. 이는 완전탐색인데 $O(N\times N!)$으로 보인다. 그러므로 불가능.
2. Knapsack
   일반적으로 d[학생의 index][불만도의 합]으로 두고 계산한다. 하지만 $N, M$ 값이 크기 때문에 성립할 수 없지만 작다고 생각하고 접근해보자.
   

   // 사실 코드는 대충써서 틀린 거 같다. ㅋㅋ
   int d[학생_index][불만도의 합] = 파묻튀 먹은 인원 수
   for(int i=0;i<N;i++){
   	for(int k=0;k<M;k++){
   		if (a[i] + k < M) { // 넣을 수 있을 때
   			d[i][a[i] + k] = max(d[i-1][k], d[i][a[i] + k] + 1)
   		} else { // 넣을 수 없을 때
   			// 여기가 핵심인데 해당 부분은 현재 index가 i인 학생을 제외 시킨다.
   			d[i][k] = d[i-1][k];
   		}
   	}
   }

   해당 부분은 현재 index가 i인 학생을 제외 시킨다.
   과연 이게 맞을까? 반례를 들겠다.
   

   3 3
   2 1 1
   ans: 1

   위 코드는 냅색으로 접근한다면 처음에 2를 가져오고 1, 1 값을 버려서 최종 값으로 2를 출력할 것이다. (틀렸으면 말해 줘라.)
   그러면 이부분을 pq를 이용해 최대로 큰 녀석을 빼서 계산한다면?
   이전 for문이 필요 없게 된다. $O(NM\log N)$을 통과시켜주는 문제는 없을 것이다.
   

생각 정리

글로 쓰다보니 조금 엉성하다. 좀 더 생각을 다듬고 글을 수정하겠다.