최대 곱의 집합

문제

자연수 N개로 이루어진 집합 중에, 각 원소의 합이 S가 되는 수의 집합은 여러 가지가 존재합니다.

최고의 집합은, 위의 조건을 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 의미합니다.

집합 원소의 개수 n과 원소들의 합 s가 주어지면, 최고의 집합을 찾아 원소를 오름차순으로 반환해주는 bestSet 함수를 만들어 보세요.

만약 조건을 만족하는 집합이 없을 때는 배열 맨 앞에 –1을 담아 반환하면 됩니다.

예를 들어 n=3, s=13이면 [4,4,5]가 반환됩니다.

(자바는 집합이 없는 경우 크기가 1인 배열에 -1을 담아 반환해주세요.)

풀이

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> bestSet(int no, int sum)
{
  vector<int> answer;

  if (sum < no)
  {
    answer.push_back(-1);
    return answer;
  }
  for (int i = 0; i < no; i++) answer.push_back(sum / no);

  int pos;
  for (int i = 0; i < sum - ((sum / no) * no); i++)
  {
    for (pos = answer.size() - 1; pos > 0; pos--)
    {
      if (answer[pos] < answer[pos - 1])
        break;
    }
    answer[pos] += 1;
  }
  sort(answer.begin(), answer.end());

  return answer;
}

int main()
{
  int         n = 3, s = 13;
  vector<int> test = bestSet(n, s);

  // 아래는 테스트로 출력해 보기 위한 코드입니다.
  for (int i = 0; i < test.size(); i++)
    cout << test[i] << " ";
}

지난 번 최소자승합 과 거의 똑같은 문제이다.

어떤 수들을 곱했을 때 가장 큰 수를 얻으려면 그 수들의 편차가 작으면 된다.

문제를 보면, 집합의 개수 n과 각 원소의 합 s가 주어졌는데 집합이 없다는 말이 있다.

이는 곧 sum이 no보다 작을 경우이다.

예를 들어 no가 7이고 sum이 5일 경우 원소는 자연수이므로

어떤 집합을 만들던지간에 곱은 0이 나올 것이다. ex. {0, 0, 1, 1, 1, 1, 1}

따라서 이 경우는 -1을 리턴 해준 것 뿐이고

나머지는 최소자승합과 같이 pos를 뒤에서부터 이동시키며 값을 추가한다.

먼저 s = 14, n = 3 으로 예를 들어보면(문제에서 s = 13)

s를 n으로 나누면 4가 된다. 따라서 벡터에 먼저 4씩 n만큼, 즉 3번을 넣어주면 벡터 원소는 {4, 4, 4}가 되고

이제 나머지 수를 계산해야한다. 우리가 만들어야 될 합은 s(14)이다. C언어의 나눗셈은 나머지를 무시하기 때문에 4+4+4=12, 즉 14에 비해 2만큼 값이 모자르게 된다.

따라서 이 2라는 값을 어떻게 공평하게 더해주는지가 핵심이며 이는 최소자승합과 같이 각 자리에 1씩 골고루 더해주는 방법이 있다. 얼마나? = 남은 수(2)만큼.

사실 이전 문제는 숫자가 일정하지 않아 if문을 통해 works[pos]와 works[pos-1]을 비교하였는데

이 문제는 직접 일정한 숫자로 벡터를 초기화하였으므로 아래와 같이 for문을 더 간단하게 만들 수 있다.

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

pos를 벡터 size로 주고 전위 연산자를 통해 6~0까지 1씩 더해준다. 물론 중간에 반복이 끝날 수 있고, 끝나지 않을 경우를 대비해서 pos가 0이면 다시 7로 만들어준다.(인덱스에서 -1은 없으니까..)

출처

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