[연습문제] 프로그래머스 level 3 최고의 집합 (Python 파이썬)

💡문제 링크

프로그래머스

 

💡문제 분석 요약

n개의 자연수로 이루어진 집합. 집합 속 각 원소의 합이 s이다.

위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합을 구하라.

만약 최고의 집합이 존재하지 않는 경우 [-1] 반

 

💡알고리즘 설계

n > s인 경우 최고의 집합이 존재하지 않으므로 [-1] 반환

while문을 사용해서 n이 0이 될 때까지 무한반복한다.

무한반복:

1. 최고의 집합의 원소 하나 s//n을 빼낸다.

2. s에서 s//n만큼 빼고, n에서 1만큼 뺀다.

이 과정을 반복하면서 최고의 집합을 찾는다.

작은 문제를 해결해서 큰 문제를 해결하는 과정이 동적 계획법(DP)와 유사하다.

동적 계획법 문제인건가..?

 

💡코드

def solution(n, s):
    result = []
    if n > s:
        return [-1]
    while n > 0:
        result.append(s//n)
        s -= s//n
        n -= 1
    return result

 

💡 오답 풀이

def solution(n, s):
    answer = 0
    if n-1 <= s:
        result = [-1]
    for i in range(1, s//2+1):
        if answer < i*(s-i):
            answer = i*(s-i)
            result = [i, s-i]
    return result

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

맨 처음에 n=2라고 가정하고 풀었던 문제.

당연하게도 모든 테스트에 통과하지 못했다.

 

💡 느낀점 or 기억할정보

어려워보이는 문제를 간단하게 풀자!