[백준 17392] 우울한 방학

www.acmicpc.net/problem/17392

17392번: 우울한 방학

그리디 알고리즘 사용

식을 사용하는 문제이다.

 

우울함의 값은 기분이 음수일때 제곱을 해서 나타내므로 음수인 날이 적어야한다.

 

음수인 날을 커버할 수 있는게 약속의 기대행복값이다.

약속의 기대 행복값은 약속 당일 h 라면 하루가 지날수록 h-1 h-2..0까지 줄어든다.

-> 그럼 약속 하나를 잡았을 때 기분이 0이상인 날은 h+1이란 의미다.

따라서 입력값을 받으면서 h+1을 sum에 더해준다.

 

이 sum이 m일의 방학동안 길다면 인호는 우울한 날이 없다. 따라서 0을 리턴한다.

그렇지 않다면 우울한 날을 최대한 분산시켜야 한다.

우울할 수밖에 없는 날은 sum = m-sum로 두고 이 sum을 최대한 분산시켜야 한다.

왜냐면 sum이 3이라 하면 1^2 + 2^ 2 + 3^2 보단 1^2 + 1^2 + 1^2가 더 작기 때문

 

그러면 우울한 날을 분산시킬 수 있는 방법은 약속이 있는 날의 수에 좌우된다.

약속이 있는 날 전후로 우울한 날을 분산시킬 수 있기 때문에 우울한 날을 n+1가지로 나눈다.

다르게 말하면 sum개의 공을 n+1의 바구니에 최대한 균등하게 담는 것이다.

예를 들어 

sum = 10, n+1이 4라고 해보자.

그러면 2, 2, 3, 3 으로 분리한후 각각 제곱합을 구해야 한다.

 

따라서 몫과 나머지를 구하고 (1 ~ 몫까지의 합) * (n+1) + (몫+1) * 나머지를 해주면 된다. 

#include <stdio.h>

using namespace std;
int n, m;
int arr[1000];
int main(void)
{
  scanf("%d%d", &n, &m);
  int sum = 0;
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
    sum += (arr[i] + 1);
  }

  int res = 0;

  int day = n + 1;
  sum = m - sum;

  if (sum > 0)
  {
    if (day >= sum)
    {
      res = sum;
    }
    else
    {
      int mok = sum / day;
      int rest = sum % day;

      res = (mok + 1) * (mok + 1) * rest;
      res += day * (mok * (mok + 1) * (2 * mok + 1)) / 6;
    }
  }

  printf("%d\n", res);

  return 0;
}