[프로그래머스 4단계] 알고리즘 34. 최고의 집합

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 34. 최고의 집합

자연수 N개로 이루어진 집합 중에, 각 원소의 합이 S가 되는 수의 집합은 여러 가지가 존재합니다. 최고의 집합은, 위의 조건을 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 의미합니다. 집합 원소의 개수 n과 원소들의 합 s가 주어지면, 최고의 집합을 찾아 원소를 오름차순으로 반환해주는 bestSet 함수를 만들어 보세요. 만약 조건을 만족하는 집합이 없을 때는 배열 맨 앞에 –1을 담아 반환하면 됩니다. 예를 들어 n=3, s=13이면 [4,4,5]가 반환됩니다.
(자바는 집합이 없는 경우 크기가 1인 배열에 -1을 담아 반환해주세요.)

#include<vector>

#include<iostream>

using namespace std;

vector<int> bestSet(int no,int sum)

{

    vector<int> answer;

    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] << " ";

}

풀이:

이 문제 역시 쉽게 풀 수 있다. 먼저 bestSet이 충족되지 않을 경우를 살펴보자. 결론부터 말하자면 bestSet이 충족되지 않을 때는 바로 원소의 개수 no가 sum보다 클 때이다 (no > sum). 왜냐하면 조건에서 모든 원소는 자연수이다. 그러니까 원소의 개수 n개일 때 벡터의 합이 최소 값일 때는 n개의 원소가 모두 1을 가질 때다. 그런데 n이 sum보다 크다면 성립이 되지 않는다. 즉 bestSet의 실패 조건은 다음과 같고 이를 만족하면 벡터에 -1을 넣어 반환시켜주면 된다.

if (no > sum)

{

answer.push_back(-1);

return answer;

}

이제 내가 세운 알고리즘을 보자.

1. sum / no 으로 나눈 값을 벡터에 넣어둔다.
2. 벡터의 총합이 sum이 될 때까지 벡터의 뒤부터 1씩 더해준다.

코드로 보면 다음과 같다.

//1. 벡터의 no 개수만큼 sum/no 를 넣어준다.

for (int i=0; i<no; i++)

answer.push_back(sum / no);

//2. 벡터의 총합이 sum이 될 때까지 벡터의 뒤에서 1씩 더해준다.

for (int i= no-1; i>= 0; i--)

{

 acc = accumulate(answer.begin(), answer.end(), 0);

if (acc >= sum)

break;

else

    answer[i] += 1;

}

그러면 간단하게 문제를 풀 수 있다. 나의 코드 전문은 다음과 같다.

vector<int> bestSet(int no,int sum)

{

    vector<int> answer;

int acc = 0;

if (no > sum)

{

answer.push_back(-1);

return answer;

}

for (int i=0; i<no; i++)

answer.push_back(sum / no);

for (int i= no-1; i>= 0; i--)

{

  acc = accumulate(answer.begin(), answer.end(), 0);

if (acc >= sum)

break;

else

     answer[i] += 1;

}

    return answer;

}

오늘의 알고리즘 포스팅을 마치겠다.