본문 바로가기

알고리즘 공부 및 문제 풀이/프로그래머스(PRO)

[pro] 프로그래머스 level3 12938 최고의 집합 (Java)

[문제]

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

[풀이]

곱의 크기가 최대가 되기 위한 수들을 생각해보면 규칙을 찾을 수 있다.

n=2, s=8이라면 [4, 4]가 최고의 집합이 될 것이다. n=3, s=9라면 [3, 3, 3]이 된다.

그렇다면 n=3, s=11이라면? [3, 4, 4]가 최고의 집합이 된다. s/n을 각 자리에 넣어준 후, 나머지가 있다면 +1씩 한 집합이 최고의 집합이 된다는 것을 알 수있다. 나머지를 한쪽으로 몬 [3, 3, 5]는 최고의 집합이 될 수 없다.

 

[코드]

 

class Solution {
    public int[] solution(int n, int s) {
        int[] answer = {};
        //n개의 숫자 합이 s
        //3개 9 -> 3 3 3
        //3개 10 -> 3 3 4
        //3개 11 -> 3 4 4
        int m = s/n;
        int r = s%n;
        if(m==0){
            return new int[]{-1};
        }
        answer = new int[n];
        for(int i=n-1; i>=0; i--){
            answer[i] = m;
            if(r>0){
                answer[i]++;
                r--;
            }
        }
        return answer;
    }
}