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

사실 이 문제의 경우 굉장히 쉬워서 그렇지, 코테에서 이렇게 수학적 풀이를 해야 하는 경우가 나오면 당황스러울 때가 많다. 보통 코테의 정잡은 수학적 풀이보다는 각종 알고리즘을 이요한 "탐색"이 정답인 경우가 많기 때문이다. 그러나 아무리 탐색을 쓰더라도 수학적 풀이를 이용해 탐색의 효율성을 증대시키는 문제가 생각보다 많기 때문에, 이런 유형에도 익숙해질 필요가 있다.

 

키 아이디어

정수 \( n \)개로 이루어진 집합이 있고, 이 집합의 합이 \( s \)일 때, 각 정수들이 가능한 한 비슷해야 곱이 최대이다. 산술평균-기하평균 부등식으로 증명할 수 있다.

 

산술평균-기하평균 부등식

산술평균-기하평균 부등식에 따르면, 양의 정수 \( x_1, x_2, \ldots, x_n \)에 대해,

\[ \frac{x_1 + x_2 + \cdots + x_n}{n} \geq \sqrt[n]{x_1 \cdot x_2 \cdot \cdots \cdot x_n} \]

여기서 등호는 모든 \( x_i \)가 같을 때 성립한다.

 

코드

def solution(n, s):
    a = s // n
    b = s % n 
    if a == 0 :
        return [-1]
    
    answer = [a]*(n-b) + [a+1]*b
    
    return answer

 

 

loewen.tistory.com