[Algorithm] 최고의 집합

프로그래머스 - 최고의 집합 문제

: 규칙을 찾아내면 쉽게 풀 수 있던 문제

문제 분석

: n과 s가 주어지면 n개의 숫자를 이용해서 합이 s가 되는 조합(집합)을 찾는데(이 때, 집합은 중복집합이라해서 중복을 허용하는 집합이다), 이중에 n개의 숫자의 곱이 가장 큰 조합을 찾아서 리턴하는 것이 문제이다.

문제 설계

: n개의 자연수를 가지고 합이 s가되는 조합을 찾는다는 관점으로 접근해보면, 단순히 완전탐색을 하면 된다. 그리고 그중에 곱이 가장 큰 조합을 찾으면 정답이다. 하지만 n이 10,000이하의 자연수라는 점을 보면 만약에 완전탐색을 하면 9^10,000의 경우의 수를 탐색해봐야 알 수 있다.. 결론은 완전탐색으로 못푼다. 따라서 어떤 규칙이 있나를 봐야하는데, 생각해보면 우리가 찾을 것은 곱이 가장 큰 조합이기에 곱이 가장 클 조건을 먼저 찾아야한다. 곱이 가장 크려면 전체 자연수 조합 속 숫자의 수가 상향평준화 돼있는 것이 좋다. 즉, 1,99 이렇게 차이가 많이나기보다는 66,60,63 이렇게 최대값이 안들어가더라도 적당히 높은수가 최대한 많아야한다는 것. 이런 관점으로 접근해보면 s보다 약간 작은 수, 즉, 하나의 수만 봤을 때는 제일 큰 수들보다는 예시의 4,5와 같이 9보다 바로 하나작은 8이 아닌 2등분했을 때 나오는 수의 근처의 수로 조합된 것이 곱이 가장 크다. 따라서 s를 n등분한 다음에 그 숫자들을 바탕으로 1씩 증가시키면서 합이 s가 되게 만들면 그 조합의 곱이 최대가 될 것이다. DP처럼 규칙을 이용해서 풀어야하는 문제라고 생각한다.

구현코드

def solution(n, s):
    answer = []
    if s < n :
        return [-1]
    num = s//n
    l = [num for i in range(n)]
    if sum(l) == s:
        return l
    else:
        idx = 1
        sum_num = sum(l)
        while sum_num != s:
            l[-idx] += 1
            sum_num += 1
            idx+=1 
        return l