[백준 - 28467번] Spell Cards - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: 그리디

마리사는 바닥에 일렬로 늘어놓은
$N$장의 카드로 마법을 연습하고 있다. 왼쪽에서부터
$i$번째에 있는
$i$번 카드의 마력 소모량은
$a_i$로 표현된다. 마리사가
$i$번 카드에 마법을 사용하기 위해서는
$a_i$만큼의 마력을 소모해야 한다.

마리사는 인접한 두 카드를 골라서 마법을 시전한다. 이때 마리사는 고른 두 카드의 마력 소모량의 합만큼 마력을 소모한다. 이후 두 카드는 그 자리에서 하나로 합쳐지며, 새로 만들어진 카드의 마력 소모량은 이전 두 카드의 마력 소모량 중 최댓값이 된다. 이 과정은 카드가 단 하나만 남을 때까지 반복한다.

마리사는 소모하는 마력을 최소화하려 한다. 이때 마리사가 소모할 마력의 양을 구해주자!

입력

첫 번째 줄에 카드의 개수
$N$이 주어진다.
$(1 \leq N \leq 400)$ 

두 번째 줄에 카드의 마력 소모량을 나타내는 정수
$a_1, a_2, \cdots, a_N$가 공백으로 구분되어 주어진다.
$(1 \leq a_i \leq 10^9)$ 

출력

마리사가 소모하는 마력의 최솟값을 출력한다.

풀이

마리사가 소모하는 마력을 최소화해야 한다.

마력 소모를 최소화하기 위해서 어떻게 해야 할까?

마력 소모가 큰 카드를 최대한 나중에 사용하는 것이 핵심이다.

왜냐하면 인접한 두 카드를 사용하고, 합쳐지는데 이때 두 카드의 마력 소모량 중 큰 카드를 기준으로 합쳐지기 때문이다.

예를 들어서 7 7 7 8 9 9 8 8 카드가 있을 때

마력 소모량이 가장 큰 9 카드를 처음부터 계속 사용한다면 9는 전체 소모량에 계속 포함될 것이다. 그러니까 가장 나중에 사용해야 하며, 합쳐지는 카드의 기준이 되는 카드 중에서 가장 작은 카드를 선택하는 것이 최선의 선택이 된다.

그래서
1. 7 7이 합쳐짐 -> 7 7 8 9 9 8 8, answer = 14;
2. 7 7이 합쳐짐 -> 7 8 9 9 8 8, answer = 28;
3. 7 8이 합쳐짐 -> 8 9 9 8 8, answer = 43;
4. 8 8이 합쳐침 -> 8 9 9 8, answer = 59;

나머지 기준 카드가 9로 다 같기 때문에 어떤 순서도 상관 없음

N은 400이기 때문에 O(N^2) 풀이도 충분히 가능하다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        
        System.out.println(answer(list));
    }
    
    static long answer(ArrayList<Integer> list) {
        long result = 0;
        
        while(list.size() != 1) {
            int min = Integer.MAX_VALUE;
            int cInd = -1;
            
            for(int i=0; i<list.size() - 1; i++) {
                if(list.get(i) <= list.get(i + 1)) {
                    //i + 1이 더 큼
                    if(min > list.get(i + 1)) {
                        min = list.get(i + 1);
                        cInd = i;
                        
                    }
                } else {
                    //i가 더 큼
                    if(min > list.get(i)) {
                        min = list.get(i);
                        cInd = i;
                        
                    }
                }
            }
            
            //합친다.
            int newCard = Math.max(list.get(cInd), list.get(cInd + 1));
            result += list.get(cInd) + list.get(cInd + 1);
            //지운다
            list.remove(cInd);
            list.remove(cInd);
            list.add(cInd, newCard);
        }
        return result;
    }
}