Today I Learned

오늘은 주말에 있을 코테를 대비해 랜덤한 코딩테스트 문제를 풀었다.

최고의 집합

https://school.programmers.co.kr/learn/courses/30/lessons/12938

문제

자연수 n개로 이루어진 중복 집합중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 한다.
1. 각 원소의 합이 S가 되는 집합
2. 각 원소의 곱이 최대가 되는 집합
n(<=10,000),s(<=100,000,000)가 매개변수로 주어질 때 최고의 집합을 return해라

풀이 과정

1. n>s면 성립되지 않으니 {-1}을 반환한다.

2. 주어진 조건을 만족하기 위해선 수학적 계산 상 숫자들 간 차이가 적어야 곱이 최대가 된다. 예를들어 n=2, s=9면 {1,8}, {3,6}보다 {4,5}의 곱이 더 크다. 그러므로 최대한 s의 값들을 균등하게 분배받는 자연수들의 집합이 해가 된다.

3. for문을 n에서 시작해서 1씩 차감하는 반복문을 만든다.

4. s를 반복문의 index인 i로 나눈 몫을 결과 배열에 기록하고, 이를 s에서 차감해 반복문을 계속 돌린다.

Java 코드

class Solution {
  public int[] solution(int n, int s) {
    if (n>s) return new int[] {-1};
    int[] result = new int[n];
    int b = 0;

    for (int i = n; i >= 1; i--) {
      int a = s/i;
      s -= a;
      result[b] = a;
      b++;
    }
    return result;
  }
}