[C++] 최고의 집합

[문제]

코딩테스트 연습 - 최고의 집합 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

합해서 s가 되는 집합 answer의 size가 n일때 answer안에 있는 값들이 무엇인지 알아봐라. 라는 문제이다.

n은 1부터 10,000이 범위이고 s는 1이상 1억 이하가 범위이다.

즉, 완전탐색으로 해당 문제를 풀면 시간초과가 날 수밖에 없다.

그러니 문제를 다시 한번 보면 어떠한 풀이법이 있을 것이라는 것을 유추할 수가 있다.

 

우선 s가 12이고 n이 3일때와 s가 12이고 n이 4일때 나올 수 있는 값이 무엇인지 3중 for문과 4중 for문을 이용해서 구해 보았다.

해당 결과는 각각 [4,4,4]와 [3,3,3,3]이었고 이를 통해서 s의 값을 n으로 나누었을때 값이 중점이 된다는 것을 유추할 수 있었다.

 

이제 만약, 나눗셈을 하고 몫이 추가로 남을때가 있다면 결과가 무엇이 되는지를 파악해보자.

s가 17이고 n이 5라면 [3,3,3,3,5]와 [3,3,3,4,4] 중에 뭐가 더 곱했을때 큰 값이 되는지를 파악해 본 결과 [3,3,3,4,4]가 더 큰 값이라는 것을 알 수가 있었다.

 

그러니 해당 문제는 반복문을 이용해 n - (s % n)만큼 s  / n 값을 넣어주고 다시 s % n 값만큼 반복하면서  s / n + 1 값을 넣어주면 된다.

밑의 코드에서 두번째 반복문에서 만일  s % n 이 0이라면 돌아가지 않을 것이기 때문에 if문 바깥으로 빼놨다.

[회고]

처음에 볼때는 어려울 줄 알았는데 생각보다 쉬운 문제였다. 정답률이 괜히 높은 문제가 아닌듯!

[코드]

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    //최대 합이 1억, 종류는 1만개. => 완탐은 안됨.
    //최고의 집합이 없는 경우에 -1 => 동점이면 없는건가?
    //3 12 => [4,4,4];
    //s를 n만큼 나눈값이 중앙값이다.
    
    if(s < n){
        answer.push_back(-1);
        return answer;
    }
    
    int temp = s / n;
    int var = s % n;
    for(int i = 0;i<n - var;i++){
        answer.push_back(temp);
    }
    for(int i = 0;i < var;i++){
        answer.push_back(temp + 1);
    }
    
    return answer;
}