[Programmers] 최고의 집합

 

[문제 설명]

 

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

 

[풀이 과정]

 

두괄식으로 풀이를 먼저 공개하자면

def solution(n, s):
    if n > s:
        return [-1]
    
    a = [(s//n) for _ in range(n-(s-((s//n)*n)))]
    b = [((s//n)+1) for _ in range(s-((s//n)*n))]

    return a+b

상당히 짧고 쉽게 풀린다.

 

하지만 이러한 풀이가 머릿속에서 바로 (짠!) 하고 떠오른 것은 아니고... 나름 시행착오를 겪었다.

 

처음에는

1. 자연수 n개로 이루어지고 각 합이 s인 집합생성 

2. 각 집합 중 곱이 가장 작은 녀석을 선택

 

이 두가지 과정을 분리해서 생각했다. 

 

구현하던 중 '어!? 그럴 필요있나? 그냥 만드면서 동시에 값을 저장해 놓고 가장 큰 값을 가진 리스트를 가져오면 되지않을까?' 라는 어리석은 발상을 하고 또 각각의 리스트를 만드는 것은 '힙을 이용하면 수행시간을 줄일 수 있겠구나!' 라는 잘못된 방향성을 갖고 구현했다.

 

from heapq import heapify, heappush, heappop

def solution(n, s):
    if n > s:
        return [-1]
    if (s//n) == (s/n):
        return [s//n for _ in range(n)]
    
    heap = [1 for i in range(n-1)]
    heap.append(s-(n-1))
    heapify(heap)  
    
    while True:
        before = heap.copy()

        low = heappop(heap)
        high = heap.pop()
        low += 1
        high -= 1

        heappush(heap,low)
        heappush(heap,high)

        if before == heap:
            return heap

뭐 이런식으로 말이다....

 

테스트 케이스의 수가 적다면 유효한 코드다. 하지만....

 

• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

 

 

ㅋ......

 

 

이 문제의 핵심은 구현이 아니다.

 

두 실수 A, B 의 편차가 작을 수록 두 수의 곱이 크다.

 

문제 해결의 핵심은 위의 수학적 지식을 알고있는가, 혹은 귀납적으로 발견할 수 있는가? 이를 물어보는 문제인 듯하다.