[programmers] level3 - 최고의 집합 python

https://school.programmers.co.kr/learn/courses/30/lessons/12938#

프로그래머스

 

※ 접근법 첫 번째 힌트,

합이 s가 되는 모든 경우의 수를 구해서, 곱했을 때 최고일 때를 구하는 것이 아니다.  효율성 테스트에서 실패

→ 어떤 숫자의 조합으로 곱했을 때 최댓값을 구하는지 딱 하나의 정답만 생각하면 된다. 

(프로그래머스는 예시 설명을 하면서 사람을 일부러 생각을 한 쪽으로만 유도하는 경향이 있는 것 같다..)

 

 

 

 

※ 접근법 두 번째 힌트, 

(첫 번째 힌트로만 못 풀었을 때, 어떤이 뭔지 감이 안 잡힐 때!)

최대가 되는 조합은, 그 요소들간 차이가 가장 적을 때 이다. 

예를 들어, 2개의 합이 9가 되는 경우에는, 두 요소간 차이가 가장 적은 {4,5}가 정답이다. 

{1,8}, {2,7}, {3,6} 다 고려할 필요 없고, {4,5}를 구하는 방법만 코드로 짜면 된다.

 

n개의 요소들끼리 차이가 가장 적으려면 당연히 s를 n으로 나누어서 나오는 값을 최소로 시작하면 된다.

 

 

※ 추가 테스트 케이스

n = 3, s = 8, [2,3,3]

n = 3, s = 6, [2,2,2]

 

 

 

---

 

 

 

정답

def solution(n, s):
    answer = []
    if n > s:	#최고의 집합이 존재하지 않는 경우
        return [-1]
    
    while n != 1:	#n의 개수만큼 요소를 모두 구해야함
    	#n 개의 요소들 끼리 차이가 가장 적으려면 최소한 s를 n으로 나눈 값으로 해야 한다.
        k = s // n		#k는 첫 번째 요소 
        answer.append(k)
        n -= 1
        if n == 1:	#모든 요소를 다 구했다면, while문 빠져나갈 조건
            answer.append(s-k)
        s -= k
        
    return answer