문제 바로가기

문제

풀이

첫 번째 풀이

자연수 S를 n개로 쪼갠 것 중, 원소의 곱이 최대가 되는 중복 집합을 반환하는 문제

예를 들어 자연수 8을 2로 쪼개보자.
첫 시작 원소는 1부터 +1씩 증가시킨다.
(1,7) (2,6) (3,5) (4,4)
이 중 원소의 곱이 최대가 되는 것은 (4,4) = 8 이다.

다음, 9를 2로 쪼개보자.
(1,8) (2,7) (3,6) (4,5)
이 중 원소의 곱이 최대가 되는 것은 (4,5) = 20 이다.

또, 이번엔 9를 3으로 쪼개보자.
첫 원소가 1일 때를 생각해보자.

• (1, {8을 2로 쪼갠 중복 집합})
  그럼 위 중복 집합에서, 원소의 곱이 최대가 되는 중복 집합이 되는 것은 무엇일까?
  => (1, {8을 2로 쪼갠 것 중 곱이 최대가 되는 중복 집합 원소})이다.
  => (1,4,4)
• (2, {7을 2로 쪼갠 것 중 곱이 최대가 되는 중복 집합 원소})
  => (2,3,4)
• (3, {6을 2로 쪼갠 것 중 곱이 최대가 되는 중복 집합 원소})
  => (3,3,3)

이 중 원소의 곱이 최대가 되는 것은 (3,3,3) = 27이다.

이런 식으로 몇 개의 예를 손으로 직접 찾아내다보면 규칙이 보인다.

각 S에 대해서 S/n개만큼의 후보 집합을 만들어낼 수 있으며,
그 중 최고의 집합이 되는 것은 S/n번째로 만들어진 집합이다.

이해가 안 된다면 위에 적은 예시들을 보자.

S가 8이고 n이 2일 때, 8/2=4개의 후보 집합을 만들어 낼 수 있다.
(1,7) (2,6) (3,5) (4,4)
또한 이 후보 집합들 중, 최고의 집합은 8/2=4번째로 만들어진 (4,4)이다.

위 규칙을 적용하여 코드를 작성하였다.

import java.util.*;

class Solution {
    static int[] dp;
    static int idx = 0;
    public int[] solution(int n, int s) {
        if(n>s) {
            dp = new int[] {-1};
        } else {
            dp = new int[n];
            dp(s, n);
        }
        Arrays.sort(dp);
        return dp;
    }
    
    static public void dp(int s, int n) {
        if(n==1) {
            dp[idx] = s;
            return;
        }
        
        dp[idx++] = s/n;
        dp(s-s/n, n-1);
    }
}

흠 효율성 테스트에서 몇 개의 테케에서 시간 초과를 얻었다.

두 번째 풀이

로직 자체엔 문제가 없는 것 같아 쓸데없이 함수를 콜하는 시간을 줄여 while문으로 바꿔보았다.

import java.util.*;

class Solution {
    public int[] solution(int n, int s) {
        int[] dp;        
        if(n>s) {
            dp = new int[] {-1};
        } else {
            dp = new int[n];
            int idx = 0;
            while(n>0) {
                dp[idx++] = s/n;
                s= (s-s/n);
                n--;
            }
        }
        Arrays.sort(dp);
        return dp;
    }
}

성공 ~~