백준 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);
}
}
Author And Source
이 문제에 관하여(백준 1500번: 최대 곱), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-1500번-최대-곱저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)