알고리즘(C++) / 프로그래머스 level 3 : 최고의 집합

level 3 : 최고의 집합

https://programmers.co.kr/learn/courses/30/lessons/12938?language=cpp 

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

 

코드

//프로그래머스 최고의 집합
#include <iostream>
#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 div = s / n; //몫
    int namuji = s % n; //나머지

    //n에서 나머지 개수 뺀 만큼
    for (int i = 0; i < n - namuji; i++) {
        answer.push_back(div);
    }
    //나머지 개수만큼
    for (int i = 0; i < namuji; i++) {
        answer.push_back(div + 1);
    }

    return answer;
}

int main() {
    int n = 2;
    int s = 9;
    solution(n, s);
    return 0;
}

 

설명

• 곱이 최대가 되는 집합을 구하기 위해서는 수들의 차가 작아야한다.
• 예로 n = 3, s = 11일 때)  여러 집합 중{3,3,5}은 원소의 곱이 45, {3,4,4}은 원소의 곱이 48이다. 이처럼 차가 가장 작은 {3,4,4} 집합이 최고의 집합이 될 수 있다.
• 몫과 나머지를 구한다.
• 나머지 수만큼 몫에서 +1한 값을 push하고, n에서 나머지 수를 뺀 만큼 몫을 push한다.

 

 

고찰

걸린 시간 : 20분

연습문제는 level에 비해 쉬운거 같다.