백준 1500번: 최대 곱

문제 설명

• https://www.acmicpc.net/problem/1500

접근법

• 조합으로 접근했다가 시간초과가 났습니다.
  • S가 최대 100, K가 최대 20으로 100C20 = 535983370403809682970이 나옵니다.
  • 중간에 Sum이 S를 넘으면 return하는 조건과 가능한 숫자는 S-K+1이라는 조건을 추가해도 너무 경우의 수가 큽니다.
• 곱하는 수들의 차이가 적을수록 전체 곱이 커집니다.

pseudocode

main(){
	int div = S를 K로 나눈 몫
	int mod = S를 K로 나눈 나머지
    곱의 최대값 = div (k-mod)개와 (div+1) mod개를 모두 곱한 값
}

정답

import java.io.*;

class Main {
	static int K;
	static int S;
	static long MaxScore = Long.MIN_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		S = sc.nextInt();
		K = sc.nextInt();
		int div = S / K;
		int mod = S % K;
		long answer = (long) (Math.pow((long) div, (K - mod)) * Math.pow((long) (div + 1), (mod)));
		System.out.println(answer);

	}

}