[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/12938
[풀이]
곱의 크기가 최대가 되기 위한 수들을 생각해보면 규칙을 찾을 수 있다.
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;
}
}
'알고리즘 공부 및 문제 풀이 > 프로그래머스(PRO)' 카테고리의 다른 글
[pro] 프로그래머스 level3 1832 보행자 천국 (Java) - dp (0) | 2023.01.30 |
---|---|
[pro] 프로그래머스 level3 12904 가장 긴 팰린드롬 (Java) (0) | 2023.01.30 |
[pro] 프로그래머스 level3 12979 기지국 설치 (Java) - 그리디 (0) | 2023.01.26 |
[pro] 프로그래머스 level3 12927 야근 지수 (Java) - 우선순위 큐 (0) | 2023.01.26 |
[pro] 프로그래머스 level3 17676 추석 트래픽 (Java) (0) | 2023.01.26 |