[알고리즘문제] 프로그래머스 - 최고의 집합

문제는 비교적 간단합니다. 다음 두 조건을 만족하는 집합을 return하면 됩니다. 입력으로 자연수의 개수 n, 합 s가 주어지고 문제의 조건은 다음과 같습니다.

 

1. 각 원소의 합이 S가 되는 집합

2. 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합

 

처음에 살짝 당황했던 부분은 s의 크기가 1억이고 자연수의 개수만 정해지고 그 자연수 경우의 수가 너무 많다는 것입니다. 그렇기 때문에 모든 경우를 검사해볼 수 없습니다.

 

일단 문제를 풀어보기 전에 제가 문제를 풀 수 있었던 핵심개념을 먼저 설명해 드리겠습니다.

 

n=2, s=10일 때 나올 수 있는 모든 경우의 수와 원소의 곱을 한번 보겠습니다.

 

1 9    -> 9

2 8  -> 16

3 7  -> 21

4 6  ->24

5 5  ->25  -> 최대인 부분

6 4 -> 24

7 3 -> 21

...

 

위에서처럼 많은 경우의 수가 나오지만 그 곱이 가장 최대가 되는 지점은 "각 원소의 값이 최대한 비슷한 값일 때" 입니다. 그렇기 때문에 4,6보다는 5,5 일때가 그 곱이 더 높게 나오는 것입니다. 저는 이 개념을 기반으로 문제를 풀었습니다.

 

그렇기 때문에 각 원소는 s/n값을 가지고 만약 나머지가 존재하는 경우 그 나머지만큼 1씩 나눠 가집니다.

 

예를 들어 n=45, s=143인 경우,

143 / 45 = 4

143 % 45 = 3

이는, (45-3)개는 각 4의 값을 가지고 나머지 3개는 1씩 더 가집니다(4+1). 아래는 그 결과입니다.

 

4 4 4 4 4 4 4 4 4 4

4 4 4 4 4 4 4 4 4 4

4 4 4 4 4 4 4 4 4 4

4 4 5 5 5

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, int s) {
    
    if(n > s){
        vector<int> result;
        result.push_back(-1);
        return result;
    }
    
    vector<int> answer(n);
    int index=0;

    int slice = s / n;
    int remain = s % n;
    
    for(int i=0;i<n-remain;i++){
        answer[index++]= slice;
    }
    for(int j=0;j<remain;j++){
        answer[index++] = slice+1;
    }
    
    return answer;
}

먼저 첫번째 for문에서는 위에서 일반적으로 4를 가지는 원소를 의미하며 두번째 for문은 나머지 3를 각각 하나씩 더 가지는 부분입니다.

 

1. 첫번째 제출(정확성1 실패, 효율성1 시간초과)

처음에는 answer에 값을 넣을 때 push_back()을 사용했고, 이 부분에서 시간초과가 나왔습니다. 아마 동적할당을 하는 부분에서 비용이 발생한 것 같아서 초기 벡터의 크기를 잡아놓고 index변수를 사용했습니다.

 

2. 두번째 제출(정확성1 실패, 효율성1 실패)

다행히 일단 시간초과 되는 부분은 해결했고, 좀 더 디테일한 부분을 신경쓰지 못한 것 같습니다.

예제를 보니 n > s보다 큰 경우는 원소로 0을 포함해야 하는데 n과 s는 모두 1보다 크거나 같다고 했기 때문에 이 부분을 예외처리 해주었습니다.