[Java] 백준 1500 (최대곱)

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

1500번: 최대 곱

 

수학 문제 알고리즘이다. 

정수 S가 주어졌을 때 갯수가 K개이고 합이 S인 양의 정수를 구해야 한다.

 

중요 로직을 말하자면 

먼저 1의 갯수가 적어야 곱이 최대로 크므로 

중간값을 많이 구해야 한다고 생각했다.

 

중요 로직 코드를 설명하겠다.

 while (true){
      if(s <= 0){
           break;
        }
      int a = s / k;
      list.add(a);
      s = s - a;
      k--;
            
} // while

먼저 s가 0 이하면 while 루프를 빠져나오는 조건문을 만들어줬다.

s를 k로 나눈 값을 구하고 a에 저장하고 list에 추가한다.

그리고 s를 나눈 값 a를 빼고 ( 하나의 정수를 구했으니 전체 값(s)에서 뺏다. )

갯수 (k) 를 하나 줄여준다.

 

 

아래는 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int s = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        if(s==k){
            System.out.println("1");
            return;
        }
        
        int max = 0;
        List<Integer> list = new ArrayList<>();
        
        while (true){
            if(s <= 0){
                break;
            }
            int a = s / k;
            list.add(a);
            s = s - a;
            k--;

        } // while

        long sum = 1;
        for (int i = 0; i < list.size(); i++) {
            sum *= list.get(i);

        }
        System.out.println(sum);
    }
}