백준 12845 - 모두의 마블 (자바 - 그리디)

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

12845번: 모두의 마블

 

* 문제 요약

모두의 마블이라는 게임에서 캐릭터 합성 이벤트를 한다.

이벤트는 다음과 같다. 순서가 매겨진 여러장의 카드가 있다. 각각의 카드는 저마다 레벨이 있다.

카드 A 에 카드 B 를 덧 붙일 수 있다. 이때 붙이는 조건은 다음과 같다.

1. 두 카드는 인접한 카드여야 한다.

2. 업그레이드 된 카드 A 의 레벨은 변하지 않는다.

 

카드 합성을 할 때마다 두 카드 레벨의 합 만큼 골드를 받는다. 골드를 최대한 많이 벌도록 해보자.

예를 들어 c1, c2, c3 로 연속된 카드 3개가 있고, 각각 레벨이 40, 30, 30 이라고 하자.

이 카드들을 합치는 과정에서 먼저 c3 에 c2 를 합쳐 임시 카드 x1 을 만든다.

x1 레벨은 30 이고, 획득 골드는 60 이다.

그 다음엔 c1 에 x1을 합쳐 카드 x2 를 만들면 레벨이 40이고 70만큼의 골드를 획득할 수 있다.

이때 획득한 골드는 70 + 60 = 130 이다.

 

다른 방법으로 c1 에 c2 를 덧붙인 카드 x1 레벨을 x1 의 레벨은 40이고 획득한 골드는 70 이다.

x1 에 c3 를 덧붙인 카드 x2 의 레벨은 40이고, 획득 골드는 70 이다. 이때 획득한 골드는 70+70 = 140 이다.

이외에 더 많은 골드를 받는 방법이 없으므로 140이 획득할 수 있는 최대 골드이다.

 

* 입력

카드의 갯수 n (1 <= n <= 1,000) 이 주어진다.

다음 줄에 각각 카드 레벨 Li 가 순서대로 주어진다. (0 <= Li <== 100,000)

 

* 출력

받을 수 있는 골드의 최댓값을 출력한다.

 

* 예시

 

* 해결 과정

획득할 수 있는 골드를 최대화 하려면 카드들끼리 합성할 때 입력받은 카드들의 레벨 중에서 최대값인 카드로 다른 모든 카드들을 합성해주면 된다.

합성 대상이 될 카드를 저장해줄 큐 하나와 레벨이 최대값인 카드를 찾았을 경우 그 값을 저장할 변수 max 를 준비한다.

이후 카드들의 갯수만큼 반복문을 돌며 현재 탐색중인 카드의 레벨이 이전에 찾은 카드의 레벨보다 큰 지 비교한다.

만약 크다면 이전에 찾아서 max 변수에 저장해주었던 카드 레벨은 큐에 적재해주고, 새로 찾은 카드 레벨의 최대값을 max 에 저장해준다.

만약 현재 탐색중인 카드의 레벨이 현재 max 값 보다 작은 경우 큐에 적재해준다.

 

반복문이 끝나고 나면 입력받은 카드들 중 최대값인 카드레벨과 다른 카드들을 큐가 완전히 빌 때까지 합성하여 획득하는 골드들을 모두 합산해주면 정답을 얻을 수 있다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());
        int result = 0;
        String[] input = br.readLine().split(" ");
        Queue<Integer> queue = new LinkedList<>();

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < count; i++) {
            int number = Integer.parseInt(input[i]);

            if (number > max) {
                if (max > Integer.MIN_VALUE) {
                    queue.offer(max);
                }
                max = number;
            } else {
                queue.offer(number);
            }
        }

        while (!queue.isEmpty()) {
            result += (max + queue.poll());
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

매 반복마다 현재 상황에서 최대값을 갱신하며 합성이 사용할 카드를 큐에 넣어주는 방식으로 최대 레벨의 카드로 합성하는 경우를 최대한 늘려 획득할 수 있는 골드의 최대값을 구했으므로 매 단계마다 최적의 판단을 (탐색중인 카드의 레벨을 기준으로 최대값 갱신 또는 큐에 적재) 하며 전체의 최적해에 가까운 정답을 찾는 그리디 알고리즘 문제에 해당된다.