[프로그래머스/C++] 최고의 집합

 

 

문제

문제 설명

 

풀이

 

  

처음에 보고 쉽다고 생각했지만, 푸는 방법에 대한 이유를 찾다보니 라그랑주 승수법을 알고 있어야 하는 문제였다.

라그랑주 승수법이란 조건부 함수의 최대화 또는 최소화 문제에 대한 해석수법의 일종인데, 이것을 지금 다루기는 어려우니 생략하려고 한다.

​

쉽게 말하면 두 식(제약조건, 목적함수)의 gradiant 방향이 같은 곳이 정답이 되는 부분인데, 쉽게 말하면 접하는 부분을 의미한다.

이 때, 방향은 같지만 크기가 다를 수 있기 때문에 라그랑주 승수를 이용해 크기를 같게 해준다.

​

[라그랑주 승수법 참고]

 

https://blog.naver.com/waterforall/222730998200

[최적화(optimization)] 3. 라그랑주 승수법(Lagrange multiplier method) / Matlab fsolve 적용

 

https://terms.naver.com/entry.naver?docId=4125258&cid=60207&categoryId=60207

라그랑주 승수법

 

 

이 정도로만 알아보고 정말 간단하게 원소가 2개인 경우를 생각해서 풀이를 쉽게 생각하고 넘어가보자.

​

제약 조건이 a+b=n 이므로,

 

$$h(a, b) = a + b - n$$
$$f(a, b) = a \cdot b$$

를 이용해 아래와 같이 표현할 수 있다.

$$L\left(a,\ b,\ \lambda \right)\ =\ f\left(a,\ b\right)\ -\ \lambda h\left(a,\ b\right)$$

이 때, 위 식을 편미분한 식이 0과 같다고 놓고 풀수있다.

​

(편미분한 식이 0과 같다고 하고 푸는 이유가 앞에서 말한 라그랑주 승수(lambda)를 이용해 그래디언트의 크기와 방향이 같게 만들었기 때문이다.)

​

편미분을 하면 두 식이 나오는데,

$$\nabla_a L(a, b, \lambda) = \nabla_a f(a, b) - \lambda \nabla_a h(a, b) = 0 \text{ ... ①}$$ 
$$\nabla_b L(a, b, \lambda) = \nabla_b f(a, b) - \lambda \nabla_b h(a, b) = 0 \text{ ... ②​}$$
$$\nabla_\lambda L(a, b, \lambda) = h(a, b) = 0 \text{ ... ③}$$
$$\lambda = b$$
$$\lambda = a$$
$$a + b - n = 0$$

위 세 식을 연립해서 풀면

$$a=b=\frac{n}{2}$$ 일 때, 최대값 임을 알 수 있다.

​

면  a=b = n2​ 일 때, 최대 값 임을 알 수 있다.

​

마찬가지로 원소가 늘어나도 같은 식으로 풀 수 있는데 결국 합이 n인 원소들의 곱이 최대가 되려면 원소들의 값이 평균이 되어야 함을 알 수 있다.

​

이 때, 원소들은 자연수여야 하므로 원소의 개수가 s면 평균값이 n/s 라고 하자.

그려면 원소들의 집합은 n/s를 내림 한 수와 n/s를 올림 한 수들의 집합으로 이루어져 있게 된다.

​

여기서 올림한 수가 몇 개인지 구하는 방법은

​

올림한 수의 개수 = n - [n/s를 내림한 수*s] 와 같이 표현할 수 있다.

​​

[아이디어 정리]

1. s개의 원소를 구하기 위해 원소의 합 n을 s로 나눠 평균을 구한다.​
2. 원소들은 자연수여야 하기 때문에 구한 평균이 0.xx와 같이 나타난다면 -1을 리턴한다.​
3. 구한 평균이 1보다 같거나 크다면 내림한 수와 올림한 수들의 개수를 구해서 return하면 된다.

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    int defaultN=s/n;
    vector<int> answer;
    if (defaultN==0)
    {
        return vector<int>(1,-1);
    }
    else
    {
        int cnt=s-defaultN*n; // +1짜리 개수
        answer=vector<int>(n-cnt,defaultN);
        for (int i=0; i<cnt; i++)
        {
            answer.push_back(defaultN+1);
        }
    }
    return answer;
}

 

---

 

문제를 풀기는 빨리 풀었는데, 왜 평균으로 바로 풀 수 있는지 설명하려다 보니 설명하는게 훨씬 오래 걸렸다...

 

프로그래머스