[DAY83] Algorithm : Best Set

자연수 $n$개의 합이 $s$가 되면서, 그 원소들의 곱이 최대가 되는 집합을 구하는 문제다. 핵심은 "곱이 최대가 되려면 수들이 최대한 균등해야 한다"는 수학적 직관이다. 이를 이용해 몫과 나머지를 계산하여 $O(N)$에 해결했다.

---

❓ 문제 분석

• 목표: 합이 $s$인 $n$개의 자연수 중, 곱이 최대인 집합을 오름차순으로 반환하기.
• 제약 조건: $n$은 최대 10,000, $s$는 최대 1억이다. $n$이 작아 보이지만 합을 만드는 조합은 무수히 많으므로 완전 탐색(DFS)은 불가능하다. 수학적 규칙을 찾아야 한다.
• 핵심 키워드: "자연수", "곱이 최대", "오름차순 정렬".

---

💡 풀이 설계

1. 시도했던 접근 (First Attempt)

• 처음에는 모든 원소를 균등하게(s/n) 맞춘 뒤, 뒤쪽 원소부터 하나씩 값을 늘려가는 방식을 생각했다.
• 하지만 vector에 값을 채워 넣는 과정(push_back)에서 뒤쪽부터 접근하려면 인덱스 처리가 번거롭다는 것을 깨달았다.

2. 최종 해결책 (Solution)

• 수학적 직관: 합이 일정할 때 곱이 최대가 되려면 수들 사이의 편차가 가장 작아야 한다. (예: $1+9=10 \rightarrow 1 \times 9 = 9$, $5+5=10 \rightarrow 5 \times 5 = 25$)
• 알고리즘 흐름:
  1. 예외 처리: $s < n$ 이면 자연수 $n$개로 합 $s$를 만들 수 없다. (최소 합이 $n$이므로) $\rightarrow$ {-1} 반환.
  2. 기본 값 배분: 모든 원소는 기본적으로 몫(s/n)을 가져야 한다.
  3. 나머지 배분: 나누어 떨어지지 않는 나머지(s%n)만큼을 $n$개의 원소 중 일부에게 +1씩 더해줘야 한다.
  4. 정렬 최적화: 오름차순으로 반환해야 하므로, 작은 수(몫)를 먼저 채우고, 큰 수(몫+1)를 나중에 채우면 sort 함수를 쓸 필요가 없다.

---

💻 코드 구현

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    // 불가능한 경우 처리 (자연수의 합 최소 조건)
    if (s < n) {
        answer.push_back(-1);
        return answer;
    }

    int quotient = s / n;   // 기본적으로 가져갈 값
    int remainder = s % n;  // +1을 해줘야 하는 원소의 개수

    // 핵심 로직: 오름차순을 위해 작은 수부터 채운다.
    // 전체 n개 중 (n - remainder)개는 몫을 그대로 가짐
    // 나머지 remainder개는 몫에 +1을 한 값을 가짐
    for (int i = 0; i < n; ++i) {
        if (i < n - remainder) {
            answer.push_back(quotient);
        } else {
            answer.push_back(quotient + 1);
        }
    }

    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: 처음 구상할 때는 일단 s/n으로 다 채우고 나서 루프를 돌며 값을 수정하려 했다.
• 해결: 굳이 값을 넣었다 뺄 필요 없이, '작은 수의 개수'와 '큰 수의 개수'를 미리 계산할 수 있다는 점을 이용했다.
  • 작은 수($s/n$)의 개수: $n - (s \% n)$
  • 큰 수($s/n + 1$)의 개수: $s \% n$
• 결과: 반복문 한 번으로 깔끔하게 해결되었고 sort 비용도 아꼈다.

---

✅ 오늘의 회고

항목	내용
유형	수학 (Mathematics), 구현
체감 난이도	하 (수학적 원리만 알면 매우 쉬움)
복잡도	시간: $O(N)$, 공간: $O(N)$
새로 배운 것	합이 일정할 때 곱을 최대로 만드는 법(편차 줄이기), 정렬 비용을 아끼는 채우기 전략