프로그래머스 Lv3 최고의 집합 C++

---

접근법

예제 1번을 보면 (1, 9) 보단 (2, 8)이 크다. 쭉 진행하다 보면 (3, 6) 보단 (4, 4)가 크다.

야근 지수 문제처럼 균등하게 분포 될 때 곱의 최대가 된다는 것을 알 수 있다!

---

풀이

s / n을 한 값을 정답에 담고, s % n 즉 나머지를 마지막 인덱스부터 추가한다.

sort를 사용하는 것보단 위의 방식이 시간 복잡도를 줄여준다.

---

코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) 
{
    if(n > s == 1) return vector<int>(1, -1);
    int div = s / n;
    int ex = s % n;

    vector<int> answer = vector<int>(n, div);
    
    int i = answer.size() - 1;
    while(ex != 0)
    {
        answer[i]++;
        i--;
        ex--;
    }
    return answer;
}