Level3 - 최고의 집합

연구하는개발자 2021. 2. 27. 01:52

728x90

programmers.co.kr/learn/courses/30/lessons/12938

코딩테스트 연습 - 최고의 집합

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만

programmers.co.kr

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

vector<int> solution(int n, int s) {
    
    vector<int> answer;


    
    if(n>s){answer.push_back(-1); return answer;}
    
    int k;
    int r;
    int p;
    
    k=s/n;
    p = s%n;
    
  
        
    for(int i =0; i<n-p;i++){
        answer.push_back(k);
     }
    
    for(int i=n-p; i<n; i++){
         answer.push_back(k+1);
    }
    
    
    return answer;
}

집합에서 s/n 값이 많을수록 모든 원소의 곱이 크다는 성질을 이용해서 푸는 문제이다.