[프로그래머스] 코딩테스트 연습 : 최고의 집합 - C++[CPP]

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

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

 

---

⊙ 문제

⊙ 제한사항

⊙ 입출력 예

⊙ 입출력 예 설명

 

---

 

⊙ 문제 접근 과정

 

n개로 이루어진 중복 집합에서 가장 큰 곱의 집합은 n의 값이 무엇이 오더라도 항상 정해져 있다.

그 값이 거의 균등하게 있어야지 곱이 가장 크다.

 

입출력의 예를 보자

n=2, s=9 일 때 result = [4,5]이다.

둘을 나누고(s/n) 나머지를 무시하고 집합을 만들면 [4,4]

그 후에 나머지 1을 더해주면 [4,5] 완성이다.

 

n=2, s=8일 때도 마찬가지이다.

둘을 나누고(s/n) 나머지는 없다. 집합을 만들면 [4,4]

 

따라서 다음과 같이 식을 세울 수 있다.

 

1. n> s이면 -1 출력
2. 모든 n개의 값에 s/n을 넣어주고
3. s/n을 넣어준 나머지 값인 s% n을 하나씩 더해주면

가장 균등한 집합이 완성되고 그 균등한 집합은 문제에서 원하는 최고의 집합이 된다.

 

위의 풀이를 그대로 코딩으로 구현해보자.

 

---

 

⊙ 문제 풀이

 

#include <vector>
#include <string>

using namespace std;

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

    if (n>s) {
        answer.push_back(-1);
        return answer;
    }

    for (int i =1; i<=n;i++)
        answer.push_back(s/n);

    for (int i = 1; i <=(s%n); i++)
        answer[n-i]++;

    return answer;
}

 

---

⊙ 마무리

 

NONE