프로그래머스 - 최고의 집합 [연습 문제]

문제 설명:

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

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

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

---

문제 예시:

n	s	result
2	9	[4, 5]
2	1	[-1]
2	8	[4,4]

---

문제 해결:

def solution(n, s):
    if s <= n-1:
        return [-1]
    elif n == 1:
        return [s]
    else:
        result = [s//n for _ in range(n)]
        
        for i in range(0, int(s%n)):
            result[-(i+1)] += 1
            
        return result

접근법은 간단하다.

기본적으로 s 가 n-1 보다 작으면 반드시 해가 없다

왜냐하면 s가 1인데 n이 3이면 [0, 0, 1]이다. 이는 해가 없다.

또한 만약에 n이 1이면 그 자체가 제일 높으므로 [s]를 준다

 

메인은 다음과 같다.

만약 n이 5, s가 23이면 [4, 4, 5, 5, 5]이다

우리가 이를 통해 알 수 있는 건 다음과 같다.

s가 22면 [4, 4, 4, 5, 5]

s가 21면 [4, 4, 4, 4, 5]

s가 20면 [4, 4, 4, 4, 4]

 

규칙이 보이는가?

그렇다. n으로 s를 나눈 값들을 1차로 list에 넣고 남은 나머지만큼 뒤에서 +1씩 해주면 가장 큰 조합이 된다.

s가 15에서 25까지 잘 생각해 보면 같은 숫자로 채워질 때까지 하나씩 +1로 늘어난다.