[백준] 1500번: 최대 곱 - Java

www.acmicpc.net/problem/1500

1500번: 최대 곱

문제

합이 S인 K개의 양의 정수 중 그 곱이 가장 큰 경우를 구하는 문제이다.

• 입력: 첫째 줄에 S와 K가 주어짐(K는 20보다 작거나 같고, S는 100보다 작거나 같으며 K보다 크거나 같다.
• 출력: 첫째 줄에 정답 출력. 답은 9,223,372,036,854,775,807보다 작다

풀이 과정

이 문제는 수학문제로, 곱하는 수의 차이가 가장 작은 경우를 구하면 된다.

 

1. S를 K로 나눠서 몫과 나머지를 각각 저장한다.

2. 몫을 K개 만큼 저장한다.

3. 나머지 수만큼 몫에 1씩 더해준다. 이외의 것들은 몫으로 남겨둔다.

4. 수를 모두 곱해서 결과를 출력한다.  

예시

입력: S=52, K=9

1. S/K = 5, S%K = 7

2. 5,5,5,5,5,5,5,5,5

3. 나머지가 7이므로 7번 반복하여 몫에 1씩 더해준다

4. 6,6,6,6,6,6,6,5,5를 곱한 곱은 6,998,400

JAVA 소스코드

출력은 9,223,372,036,854,775,807보다 작으므로 변수는 모두 long형으로 선언한다.

 

※ 자바의 기본 자료형(primitive type) 정수형의 범위

이름	바이트 수	범위
byte	1	-127 ~ +128
short	2	-32,768 ~ + 32,767
int	4	-2,147,483,648 ~ +2,147,483,647
long	8	-9,223,372,036,854,775,808 ~+9,223,372,036,854,775,807

* 백준에 자바코드로 올릴경우, class이름은 반드시 Main으로 해야하고 패키지명은 제외해야한다. 아니면 런타임에러 뜬다. 본인도 처음에 몰라서 알수없는 Runtime에러때문에 당황했었다.

 

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        List<Long> list = new ArrayList<>();//k개의 정수를 저장할 리스트
        long result = 1; //k개의 정수를 곱한 결과
        long s = scan.nextInt();
        long k = scan.nextInt();
        long div = s/k; //s를 k로 나눈 몫
        long res = s%k; //나머지

        //몫을 k개만큼 저장
        for(int i=0;i<k;i++){
            list.add(div);
        }
        //나머지만큼만 1씩 더함
        for(int i=0;i<res;i++){
            list.set(i,(list.get(i)+1));
        }
        //result에 k개의 정수를 곱함
        for(int i=0;i<list.size();i++){
            result *= list.get(i);
        }

        System.out.println(result);
    }
}