15903 카드 합체 놀이

자바 / 실1 / 그리디 알고리즘

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

 

알고리즘을 생각해 내는 것도 쉬웠고, 알고리즘을 생각해 낸 다음에는 푸는 데 20분도 걸리지 않았다.

 

다만, 최대 입력을 받는 경우 그 합이 int의 범위를 넘어가 오버플로우가 날 수 있는 경우를 고려하지 않아 sum과 arr의 자료형을 long으로 바꾸어 다시 풀어서 맞았다.

 

알고리즘: 매 순간 가장 작은 수 두 개를 더하는 방식으로 진행하면 쉽게 풀 수 있다.

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

public class Main
{
    private static int n, m;
    private static long sum = 0;
    private static long[] arr;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new long[n];

        s = br.readLine();
        st = new StringTokenizer(s);

        for(int i = 0; i < n; i++)
        {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        for(int i = 0; i < m; i++)
        {
            arr[0] = arr[0] + arr[1];
            arr[1] = arr[0];
            Arrays.sort(arr);
        }

        for(int i = 0; i < n; i++)
        {
            sum += arr[i];
        }

        System.out.println(sum);
    }
}