최소자승합(제곱의 합) 구하기

문제

회사원인 수민이는 많은 일이 쌓여 있습니다.

수민이는 야근을 최소화하기 위해 남은 일의 작업량을 숫자로 메기고, 일에 대한 야근 지수를 줄이기로 결정했습니다.

야근 지수는 남은 일의 작업량을 제곱하여 더한 값을 의미합니다.

수민이는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다.

수민이의 퇴근까지 남은 N 시간과 각 일에 대한 작업량이 있을 때, noOvertime 함수를 제작하여 수민이의 야근 지수를 최소화 한 결과를 출력해 주세요.

예를 들어, N=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 일을 한 결과는 [2, 2, 2]가 되고 야근 지수는 2² + 2² + 2² = 12가 되어 12를 반환해 줍니다.

풀이

문제 이름은 야근 지수라고 붙었는데 문제를 잘 읽어보면 최소자승합 알고리즘이다.

쉽게 말해 다음과 같다.

어떤 수들이 있다. 그 수들 중 특정 수에서 1씩 testNo 횟수만큼 뺀다.

그 후 모든 수들을 각각 제곱해서 더했을 때 최솟값이 나오게 하는 알고리즘이다.

10이란 숫자를 3개(더해서 10이되게)로 나누면 어떻게 나눌 수 있을까?

1, 3, 6 또는 3, 2, 5 이런 식으로 나눌 수 있을 것이다.

그렇다면 각각의 제곱의 합은 얼마인가? 전자의 경우 1 + 9 + 36 = 46이 될 것이고 후자의 경우 38 이 될 것이다.

여기서 알 수 있는 사실은 자승합은 각 숫자 편차가 적을 수록 최솟값을 가진다는 것이다.

따라서 10에서 최소자승합을 구하기 위해서는 3, 3, 4와 같이 편차가 적게 나누면 34를 가진다.

구현 역시 직관적으로 구현한 이유로 어려운 부분은 없을 것이다.

미리 숫자를 정렬해두고 조금이나마 내부 for문의 연산량을 줄이는 것을 목표로 하였다는 점을 제외하면

그다지 어려운 코드는 아니지만 최소자승합의 개념을 도출하는 것이 중요한 포인트라 생각한다.

소스 코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int noOvertime(int no, vector<int> works)
{
  int answer = 0;

  sort(works.begin(), works.end());  // sorting
  int Max, pos;

  for (int i = 0; i < no; i++)
  {
    for (pos = works.size() - 1; pos > 0; pos--)
    {
      if (works[pos] > works[pos - 1])
        break;
    }
    works[pos] -= 1;
  }
  for (int i = 0; i < works.size(); i++)
  {
    answer += works[i] * works[i];
  }

  return answer;
}

int main()
{
  vector<int> works{ 4, 3, 3 };
  int         testNo = 4;

  int testAnswer = noOvertime(testNo, works);

  cout << testAnswer;
}

알고리즘 연습 Level 3 | 프로그래머스