문제 풀이

약속의 기대 행복값이 $H_{i}$라면 이 행복값으로 기분을 음수가 되지 않게 유지할수 있는 날짜는 $H_{i}$ + 1일 이다.(행복값이 2라면 2, 1, 0으로 3일을 유지할 수 있음)

그러면 유지할 수 있는 날짜를 모두 더하고 방학의 기간 m에서 빼면 인호가 기분이 우울한 날짜의 총 합을 알 수 있다. 그 날을 적절히 분배를해서 최대한 덜 우울하게 만들어야한다.

그렇게 하려면 최대한 골고루 분배를 해서 최대한 숫자가 작게 만들어 줘야한다.

약속의 개수가 n개라면 n + 1개의 분배 장소가 정해진다. n+1개의 구간에 최대한 균등하게 분배해야 한다. 그렇게하려면 n+1개의 구간에 1씩 각각 한개씩 순회하면서 우울한 날을 넣어주면된다.

문제 링크

boj/17392

소스코드

PS/17392.java

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int []arr= new int[1001];
    static int []arr2= new int[1001];
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int val = 0;
        for(int i=0;i<n;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            val += arr[i]+1;
        }
        int left = m - val;
        if(m<=0)
        {
            System.out.println(0);
            return ;
        }
        while(true) {
            for (int i = 0; i < n + 1; i++) {
                if (left <= 0)
                    break;
                arr2[i]++;
                left--;
            }
            if(left<=0)
                break;
        }
        int ans =0;
        for(int i=0;i<n+1;i++) {
          for(int j=1;j<=arr2[i];j++)
          {
              ans += j*j;
          }
        }
        System.out.println(ans);
    }
}