[Programmers]Python_최고의 집합

문제

 

문제 설명

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

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

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

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

 

제한사항

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

코드

def solution(n, s):
    #합이 숫자 개수보다 작으면 만들 수 없는 경우임
    if n > s:
        return [-1]
    #합이 숫자 개수와 같으면 모든 숫자가 1인 경우밖에 없음
    if n == s:
        return [1] * n
    
    #합을 숫자의 개수로 나눈 몫 (숫자의 개수만큼 등분한 값)
    end = s // n
    
    #숫자의 개수로 나눈 나머지가 0이면 모든 숫자가 n일때 최고의 집합이 됨
    if s % n == 0:
        return [end] * n
        
    #나머지가 0이 아니면
    else:
        #일단 answer에 모든 숫자를 end로 n개만큼 집어 넣고
        answer = [end] * n
        #나머지만큼 뒤에서부터 1씩 더해주면 최고의 집합이 됨
        for i in range(s % n):
            answer[i] += 1
        return sorted(answer)

 

진행 과정

 

예제 #1

n = 2

s = 9

 

위 예제를 보면 숫자의 개수가 2개일때 합이 9가 나와야하는 집합을 구해야하는 문제이다.

 

우선 합이 9가 나와야하는 집합을 구하는데 앞서 합이 8이 나와야하는 집합을 생각해보자.

{ 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 }, { 5, 3 }, { 6, 2 }, { 7, 1 }

총 7개의 집합이 나오지만 뒤의 3개는 앞에서 이미 나온 { 1, 7 }, { 2, 6 }, { 3, 5 } 의 원소 곱과 같으므로 무시해도 되는 값들이다. 따라서 8 // 2 까지만 찾아보면 된다는 것이 된다.

 

그러면 { 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 }에서 원소의 곱이 가장 큰 값이 무엇일까??

당연히 마지막 { 4, 4 }이 될 것이고 이것은 합을 숫자의 개수만큼 등분한 값만을 원소로 가지는 집합이다.

 

합이 8일때는 딱 { 4, 4 }로 나누어 떨어져서 최고의 집합을 구하기 쉽다. 그렇다면 합이 9일때는 어떻게 해야할까...

위에서 설명했듯이 숫자의 개수만큼 등분한 값까지만 집합을 찾아보면 된다.

{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } ... (뒤에는 찾아볼 필요가 없다.)

여기서도 { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 중에 원소의 곱이 가장 큰 집합은 마지막 집합 { 4, 5 }이다.

이것은 { 4, 4 } 에서 마지막 원소 + 1을 한 값과 같다. 그리고 +1 은 9 % 2 = 1과 같다.

 

만약에 4개의 숫자로 합 15를 찾는다고 해보자.

(집합이 너무 많이 나와서 생략...)

{ 3, 4, 4, 4 }가 최고의 집합으로 나온다.

이것은 { 3, 3, 3, 3 }에서 뒤에서부터 +1을 해준 값이다. 어디까지?? 4 % 15 의 값만큼 간 인덱스까지 +1을 해준다.

 

위 코드에서는 그냥 range(s%n)으로 구현하여 앞에서부터 +1을 해주었는데 이렇게 해주면 { 4, 4, 4, 3 }이 되지만 sort를 해주면 { 3, 4, 4, 4 }로 바르게 나온다.

 

코드에서의 진행과정은 위 설명으로 충분하다고 생각되어 생략하겠습니다.