- Date : 2021.02.20(토)
- Time : 20분
- 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.
각 원소의 합이 S가 되는 수의 집합
위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합
예를 들어서 자연수 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 이하의 자연수입니다.
answer = []
if s < n :
return [-1]
for _ in range(n):
answer.append(s//n)
# s//n 으로 떨어지는 숫자를 n개만큼 넣어줌 -> 최대한 균등한 숫자를 만들기 위해
indexs = len(answer)-1
# 맨 뒤의 인덱스부터 +1을 해주기 위해 !
# 0부터 하고싶으면 for문 이후에 sort를 해주면 되긴하다
for i in range(s - sum(answer)):
# 현재 answer에 들어있는 숫자에서 부족한만큼 for문을 돌린다
answer[indexs] += 1
# 맨 뒤의 인덱스부터 +1을 넣어준다.
indexs -= 1
# 값이 남았다면 그 앞에 인덱스에도 넣어주기 위해 -1을 해준다.
return answer: 먼저 처음 문제를 봤을 때 생각은 모든 조합을 구한 뒤 그 중에서 곱이 제일 큰 걸 찾는것이 좋지 않을까? 라고 생각을 했지만, 이것은 숫자가 작을 때는 괜찮지만 숫자가 커지면 효율성이 아주아주 떨어지게된다..😥 어떤 경우에 곱셈이 가장 크겠나? 라는 생각을 해보면 곱셈을 하는 숫자끼리 차이가 크지 않아야지 가장 큰 곰셉을 만들어낼 수 있다는 것을 깨달았다! (18 보다 44가 큰것처럼!)
예시를 들어보자면 n = 3, s = 10 일 때, 먼저 10//3 = 3을 균등하게 n(=3)만큼 answer에 넣어준다. answer = [3,3,3] 이 때 answer의 합을 보면 9 이고 s에서 1만큼 모자라기 때문에 answer에 한 원소에 +1을 해주면 완성되는 것이다! 곱셈을 하는 숫자끼리 차이가 제일 크지 않을 때 최대 곱이 된다는 걸 알아야한다...!