프로그래머스 / 최고의 집합 / python

처음 시도한 방법

from itertools import combinations_with_replacement

def solution(n, s):
    answer = []
    t = []
    for com in combinations_with_replacement(range(1,s), n):
        if sum(com) == s:
            t.append(list(com))
            
    t.sort(key= lambda x: x[0], reverse=True)

    if len(t):
        return t[0]
    else:
        return [-1]
    

말도 안되는 방법이다. 모든 테스트 케이스에 대해 시간초과가 떴다.
다시 생각해도 너무 말이 안돼서 뭐라 쓸 말이없다.

다음 시도 코드

def solution(n, s):
    answer = []
    if n > s:
        return [-1]

    t = s // n
    answer = [t] * n
    
    idx = n-1
    while sum(answer) != s:
        answer[idx] += 1
        idx -= 1
    
    return answer

수학적 사고로 해결해야할 문제이다.
이 문제에서 생각할 바는 각 원소의 곱이 가장 큰 경우가 정답인 것이다. 즉 같은 수가 많은 쪽이 유리하다. 그래서 위에와 같이 t = s//n, answer = [t] * n 이런식으로 처음에 시작한다.

그 다음 조건인 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주야하므로 뒤에서 부터 1씩 증가 시키면서 정답을 구할 수 있다.

하지만 위코드는 while 문을 돌때마다 sum을 구하므로 효율적이진 않다.

def solution(n, s):
    answer = []
    if n > s:
        return [-1]

    t = s // n
    answer = [t] * n
    
    idx = n-1
    t = sum(answer)
    while t != s:
        answer[idx] += 1
        idx -= 1
        t += 1
    
    return answer

sum을 매번 구하지 않고 처음에 구한 다음 1씩 증가 시키는 방법으로 해결

---

이런 수학적 사고를 필요로하는 문제를 처음으로 스스로 해결한 것 같다.
하지만 2번째 코드처럼 비효율적인 방법은 테스트 케이스를 돌려봐야만 깨닫는다. 처음 코드 짤때도 이러한 부분을 생각하면서 해야한다..