[프로그래머스] 최고의 집합

[프로그래머스] 최고의 집합

코딩테스트 연습 - 최고의 집합 | 프로그래머스

 

자연수1 + 자연수2 + ... + 자연수n = S

이면서

자연수1 * 자연수2 * ... * 자연수n 이 최대가 되는 집합

 

자연수를 중복해서 사용할 수 있다.

숫자를 주어진 n개의 범위에서 최대한 곱을 크게 만드는 것이 관건이다.

 

테스트케이스를 세개정도 잡아서 나오는 숫자를 나열해보았다.

 

2개의 자연수로 6의 수를 만든다고 가정하면

[1, 5] = 5

[2, 4] = 8

[3, 3] = 9

가 나온다.

여기서 곱이 최대가 되는 것은 [3, 3]

 

3개의 자연수로 6의 수를 만든다고 가정하면

[1, 1, 4] = 4

[1, 2, 3] = 6

[2, 2, 2] = 8

여기서 곱이 최대가 되는 것은 [2, 2, 2] 이다.

 

문제에 나와있는 테스트 케이스의 경우에도

n = 2, s = 9일 때

[4, 5]

 

n = 2, s = 8일 때

[4, 4]

 

이렇게 테스트 케이스를 나열해보니

배열에 모든 원소들의 원자값이 비슷한 크기를 가지는 것이 정답이된다고 볼 수 있다.

 

이 조건을 가지고 나올 수 있는 배열들을 정답이라고 가정하고

다시한번 하나의 숫자를 가지고 n값을 조정 하며 나열해보았다.

 

n	s	정답 배열
1	9	[9]
2	9	[4, 5]
3	9	[3, 3, 3]
4	9	[2, 2, 2, 3]
5	9	[1, 2, 2, 2, 2]
6	9	[1, 1, 1, 2, 2, 2]
7	9	[1, 1, 1, 1, 1, 2, 2]
8	9	[1, 1, 1, 1, 1, 1, 1, 2]
9	9	[1, 1, 1, 1, 1, 1, 1, 1, 1]
10	9	[-1]

 

숫자를 나열해보니 보이는 규칙이 있다.

• 배열에는 s를 n으로 나누었을 때 나오는 몫이 항상 들어간다
• s를 n으로 나누었을 때 나머지 갯수만큼 몫이 아닌 값이 들어간다
• 몫이 아닌 값들이 몫보다 1크다
• n이 s보다 작은 배열은 만들 수가 없다

이와 같은 규칙들을 발견했고

이 규칙대로 코드를 구현했다

• n이 s보다 크면 { -1 } 을 반환한다.
• s/n를 구한다.
• n - s%n 갯수만큼 answer에 몫을 넣는다.
• s%n 갯수만큼 answer에 몫+1을 넣는다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    if(n > s) return {-1};
    int div = s / n;
    int mod = s % n;
    for(int i = 0; i < n-mod; i++){
        answer.push_back(div);
    }
    for(int i = 0; i < mod; i++){
        answer.push_back(div+1);
    }
    return answer;
}