[ 알고리즘 ] 코딩 - Programmers - 최고의 집합.java

---

문제 링크

programmers.co.kr/learn/courses/30/lessons/12938

코딩테스트 연습 - 최고의 집합

---

문제 개요

프로그래머스 - Level 3 - (자바) 최고의 집합 - 규칙 찾기, 나누기 규칙?

문제 설명

제한 사항

입출력 예시

자연수 n개로 이루어진 중복 집합 중 각 원소의 합이 s가 되고, 그중에서도 각 원소의 곱이 최대인 것을 구하는 문제

---

로직

이 문제는 규칙을 찾는 문제이다. 3가지의 규칙에 맞게 코드를 구현하자

Step 01. n 이 s보다 큰 경우에는 어떠한 경우에도 원소가 있을 수 없으므로 배열에 -1만 담아서 return

Step 02. s가 n으로 딱 나누어 지는 경우. 다른 모든 경우의 수보다도 나눈 수들의 곱이 가장 큰 값이다.

즉, 배열에 s/n한 값을 n개만큼 담아서 return

Step 03. s가 n으로 딱 나누어지지 않는 경우. 일단 s/n 인 divide를 구하자.

그리고 나눈 값에서 몇개의 원소에 +1 할 수 있는지 찾자. ( s - divide*n)

그 갯수만큼 원소에 +1 해주고 return 하면 정답!

예시

 

위와 같이 되는 이유는 그 어떤 값을 찾더라도, s에서 n으로 나눈 값이 가장 커질 수 있는 값이기 때문이다. 

( n이 4, s가 12인 경우 3 3 3 3 이 되는 것을 보면 알 수 있다. )

---

코드

class Solution {
	public int[] solution(int n, int s) {
		if (n > s) { // 무조건 -1
			int[] ans = { -1 };
			return ans;
		}

		if (s % n == 0) { // 딱 나누어 지는 경우
			int divide = (int) Math.ceil(s / n);
			int[] answer = new int[n];
			for (int i = 0; i < n; i++) {
				answer[i] = divide; // 나눈 값을 전체 배열에
			}
			return answer;
		}
		// 그 외의 경우. 딱 나누어지지 않는다
		int divide = (int) Math.ceil(s / n); // 나눈 값 저장
		int diff = s - divide * n; // 나누고 몇개의 원소에 +1 할수있는지 판단
		int[] answer = new int[n];
		for (int i = n - 1; i >= 0; i--) {
			if (diff-- > 0) // 해당 원소의 수만큼 더해줌
				answer[i] = divide + 1;
			else // 다 더했으면 나눈값으로!
				answer[i] = divide;
		}
		return answer;
	}
}