[알고리즘] 프로그래머스 최고의 집합 파이썬 | 구현

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

문제

나의 풀이

합이 S가 되는 여러 쌍 중 곱이 최대인 쌍은 무조건 수가 가운데에 몰려 있다.

예시 ) n = 2 , S = 10

합이 10이 되는 {1, 9} {2, 8} {3, 7} {4, 6} {5, 5} 중 곱이 최대인 쌍은 {5, 5}이다.

수학적으로 풀이하자면
{5, 5}의 곱은 x^2로, {4, 6}의 곱은 (x-1)(x+1)로 나타낼 수 있다. 식을 통해 모든 곱을 비교하면

x^2 > (x-1)(x+1) > (x-2)(x+2) > (x-3)(x+3) > ...

무조건 위 식을 만족하기 때문에 x^2가 최대가 되며 가운데에 몰려 있는 쌍이 다른 모든 쌍들보다 큰 곱을 가진다.

나누어 떨어지지 않는 경우에도 마찬가지로 쌍이 최대한 가운데에 몰리게 하면 된다.
S를 n으로 나눈 몫을 나누어 갖고, 나머지를 1씩 고르게 분배함으로써 수의 쌍을 가운데에 위치시킨다.

def solution(n, s):
    if (t := s // n) == 0:
        return [-1]
    answer = [t] * n
    for i in range(n-1, n-s%n-1, -1):
        answer[i] += 1
    return answer

다른 풀이

def solution(n, s):
    if s < n:
        return [-1]
    answer = []

    for _ in range(n - s % n):
        answer.append(s // n)
    for _ in range(s % n):
        answer.append(s // n + 1)
    return answer

결국 수의 쌍을 가운데로 몰고자 하는 행위는 같다.

얻어가기