[BaekJoon] 1500 최대 곱

1.  문제 링크

2.  문제

요약

• 정수 K와 S가 주어졌을 때, 합이 S인 K개의 양의 정수를 찾고 여러 개일 경우 그 곱을 최대로 하려고 합니다.
• 곱을 최대로 했을 때의 값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 20보다 작거나 같은 수인 K와 K보다 크거나 같고 100보다 작거나 같은 수인 S가 주어집니다.
• 출력: 첫 번째 줄에 곱을 최대로 했을 때의 곱을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public long getMaxMultiply(int s, int k) {
		int[] nums = new int[k];
		int div = s / k;
		int remain = s % k;
		for(int i = 0; i < nums.length; i++) {
			nums[i] = div;
		}
		for(int i = 0; i < remain; i++) {
			nums[i]++;
		}
		long mul = 1;
		for(int i = 0; i < nums.length; i++) {
			mul *= nums[i];
		}
		return mul;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		br.close();
		StringTokenizer st = new StringTokenizer(input);
		int s = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		Main m = new Main();
		bw.write(m.getMaxMultiply(s, k) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 곱을 최대로 하기 위해서는 각 수들 간의 차이가 적어야지만 곱을 최대로 할 수 있습니다.
• 그렇기 때문에 주어진 S에 대해서 K로 나눈 후에 나온 몫 K개에 나머지 R에 대하여 몫 R개에 1씩 나누어주어 R개의 (몫 + 1)과 (K - R)개의 몫을 곱한 값이 곱을 최대로 한 값이 됩니다.

1. 주어진 S를 K로 나눈 몫을 K개의 1차원 배열에 설정합니다.
2. 1차원 배열의 index 0부터 (S를 K로 나눈 후 나온 나머지 - 1)만큼 1씩 더해줍니다.
3. 1차원 배열에 있는 값들을 모두 곱한 후에 출력합니다.