[SWEA - Java] 1265. [S/W 문제해결 응용] 9일차 - 달란트2

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18R8FKIvoCFAZN 

설명

묶음을 어떻게 나눠야 할까? DP? 완전 탐색?

잘 생각해보자.

 

10 달란트를 3묶음으로 나눌 경우 어떻게 나누어야 가장 많은 사탕을 교환할 수 있을까?
각 묶음에 들어있는 달란트 수의 차이가 최소여야 곱했을 때 얻는 사탕의 수가 크다

 

즉, N개를 묶음 P로 나눈 각 묶음의 숫자의 차이가 작아야만 곱했을 때 값이 커진다.

이렇게 되면 문제는 쉬워진다.

 

N개를 말 그대로 N / P만큼으로 나누자.

나머지가 생길 수 도 있고 안 생길 수도 있다.

나머지가 안 생기면 그대로 N / P만큼으로 나누고 끝인 거고,

나머지가 있다면 각 남은 숫자를 각 묶음에 하나씩 더해준다면 가장 작은 차이가 날 것이다.

 

아래 표를 보면 3 * 3 * 4(10 달란트로 얻는 사탕의 수가 가장 큰 경우)로 각 묶음의 차가 0, 0, 1 밖에 나지 않는다.

 

10 달란트
1	*	1	*	8	=	8
3	*	3	*	4	=	36

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Solution {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
			int P = Integer.parseInt(st.nextToken());
			
			int[] arr = new int[P];
			Arrays.fill(arr, N/P);
			
			int count = N % P;
			for(int i = 0; i < arr.length; i++) {
				if(count != 0) {
					arr[i] += 1;
					count--;
				} else {
					break;
				}
			}
			
			long answer = 1;
			for(long i : arr) {
				answer *= i;
			}

			sb.append("#" + test_case + " " + answer + "\n");
		}

		System.out.println(sb.toString());
	}
	
}