백준 20413 - MVP 다이아몬드(Easy) (자바 - 그리디)

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

20413번: MVP 다이아몬드 (Easy)

 

* 문제 요약

- 입력 제한 외 난이도에 따른 문제의 차이는 없다.

상민이는 게임 단풍잎이야기에 과금을 즐겨한다. 단풍잎이야기에는 과금액에 따라 혜택을 제공하는 MVP 등급이 존재한다.

MVP 등급은 브론즈(B), 실버(S), 골드(G), 플래티넘(P), 다이아몬드(D) 로 총 다섯등급이 있으며, 현재 달과 지난달, 즉 현재 달을 포함한 최근 2개월간의 과금액으로 결정된다.

단, 단풍잎이야기에는 과도한 과금을 막기 위해 '최대 과금 한도' 가 있어 한 달에 최대 다이아몬드 등급 기준액 까지만 과금할 수 있으며, 만원 단위로만 과금이 가능하다.

 

MVP 등급은 해당 달이 끝날 때 계산되어 책정된다. 예를 들어 아래의 표와 같은 등급 기준액을 따르고 1월에 게임을 시작한 상민이가 1월에 30만, 2월에 20만, 3월에 50만원을 과금했다면 1월(30만) 과 2월(30+20=50만) 에는 실버 등급, 3월(20+50=70만) 에는 골드 등급으로 책정된다.

 

상민이는 게임을 시작하고 N개월 동안 수많은 현금을 과금해왔다. 상민이는 이 사실을 자신의 여자친구에만큼은 철저히 비밀로 하고 있었다. 상민이의 여자친구는 상민이가 게임에 과금하는 것을 매우 싫어했기 때문이다.

그러던 어느 날 문제가 발생했다. 상민이의 여자친구에게 N개월간의 MVP 등급 기록이 유출된 것이다!

상민이의 여자친구는 상민의 과금액을 역추적하기 위해 당신에게 부탁했다.

- 상민이의 여자친구 : 상민이가 게임에 최대 얼마나 과금한건지 알려줘

둘 사이에 어떤일이 벌어질지는 모르겠지만, 당신은 상민이의 여자친구를 위한 프로그램을 작성해야만 한다.

 

* 입력

첫 번째 줄에는 게임을 플레이한 개월 수 N이 주어진다.

두 번째 줄에는 실버, 골드, 플래티넘, 다이아몬드 등급 기준액 s, g, p, d 가 만원 단위로 순서대로 주어진다.

브론즈 등급 기준액은 0원이다.

세 번째 줄에는 게임을 플레이 한 첫 번째 달부터 N번째 달 까지의 MVP 등급이 등급 표기대로 주어진다.

기록과 같은 MVP 등급 달성이 불가능한 경우는 주어지지 않는다.

 

* 출력

입력된 MVP 등급을 달성하기 위한 최대 누적 과금액을 만원 단위로 출력한다.

 

* 제한

- 1 <= N <= 36

- 0 < s < g < p < d <= 500

- 상민이가 한번 달성한 MVP 등급은 줄어들지 않는다.

 

* 예시

 

* 해결 과정

입력받은 각 등급을 달성하기 위한 최대값을 구해야 하므로 각 등급별 단위 내부에서 다음 등급으로 넘어가기 바로 직전의 가격을 기준으로 과금을 했다고 판단해야 한다.

여기서 최근 2달간의 과금액을 기준으로 등급을 결정하게 되므로 매 반복마다 이전 달의 과금액을 남겨놓은 상태에서, 이전 달의 과금액을 기준으로 현재 달에 받은 등급을 달성하는데 필요한 최대 금액을 계산해줘야 한다.

 

현재 등급을 달성하기 위한 최근 2달간의 최대 과금액을 구하기 위해 해당 등급을 달성하기 위한 금액에서 1을 뺀 다음, 이전 달의 과금액을 다시 한 번 빼서 현재 달의 과금액을 구해줬다.

다이아 등급의 경우 최대 과금 한도에 해당하므로 다이아 등급이 입력으로 들어온 경우 반대로 다이아 등급을 달성하기 위한 최소 금액을 저장하였다.

그렇게 하여 현재 달의 과금 금액이 결정되면 result 변수에 합산해준다.

 

그러므로 코드는 다음과 같아진다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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());
        char[] grade = new char[count];
        String[] input = br.readLine().split(" ");
        int silver = Integer.parseInt(input[0]);
        int gold = Integer.parseInt(input[1]);
        int platinum = Integer.parseInt(input[2]);
        int diamond = Integer.parseInt(input[3]);

        String str = br.readLine();
        for (int i = 0; i < str.length(); i++) {
            grade[i] = str.charAt(i);
        }

        int result = 0;
        int current = 0;
        for (int i = 0; i < grade.length; i++) {
            if (grade[i] == 'B') {
                current = (silver - 1) - current;
            } else if (grade[i] == 'S') {
                current = (gold - 1) - current;
            } else if (grade[i] == 'G') {
                current = (platinum - 1) - current;
            } else if (grade[i] == 'P') {
                current = (diamond - 1) - current;
            } else if (grade[i] == 'D') {
                current = diamond;
            }

            result += current;
        }

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

 

현재 상황에서 최적의 해답을 선택한다. -> 각 등급을 달성하는데 필요한 현재 달의 최대 금액을 계산하여 최종금액에 합산해준다.

선택된 해답이 조건을 만족하는지 검사한다. -> 매 반복 단계에서는 전체 최대 과금액을 구할 수 없으므로 게임을 플레이한 총 개월 수 동안 전체 과금 최대금액을 구할 때까지 반복을 계속한다.

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘 문제에 해당된다.