백준 12845번: 모두의 마블 (Python/Java)

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

12845번: 모두의 마블

 

 

 

접근

---

현재 가장 많은 골드를 얻을 수 있는 선택이 최종적으로도 가장 많은 골드를 얻을 수 있는 방법이 된다는 점을 통해 그리디 알고리즘 문제라는 것을 파악할 수 있었다. 그렇다면 현재 선택에서 가장 많은 골드를 얻을 수 있는 방법이 뭘까?

 

복잡하게 생각할 것 없이 내가 지금 가지고 있는 카드의 구성을 떠나서 가장 높은 레벨의 카드에 그것보다 작은 레벨의 카드들을 덧붙여준다면 현재 받을 수 있는 골드 중 가장 높은 골드를 받을 수 있는 조합을 만들 수 있게 된다. 즉, 내가 가지고 있는 조합에서 가장 높은 레벨을 가지고 있는 카드를 구해 나머지 레벨을 더해나가면 된다. 나 같은 경우는 간단하게 sort를 이용해서 가장 높은 값을 구했다.

 

 

 

풀이

---

Python

cardNum = int(input())

cardList = []
card = (input()).split()
for i in range(cardNum):
    cardList.append(int(card[i]))
    
cardList = sorted(cardList, reverse=True)

result = 0
for i in range(1, cardNum):
    result += (cardList[0] + cardList[i])

print(result)

 

Java

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
        int cardNum = Integer.parseInt(scan.nextLine());

        Integer[] cardList = new Integer[cardNum];
        String[] card = (scan.nextLine()).split(" ");
        for(int i = 0 ; i < cardNum ; i++){
            cardList[i] = Integer.parseInt(card[i]);
        }

        Arrays.sort(cardList, Collections.reverseOrder());

        int result = 0;
        for(int i = 1 ; i < cardNum ; i++){
            result += (cardList[0] + cardList[i]);
        }

        System.out.println(result);

    }

}

 

 

 

후기

---

굉장히 쉬운 문제였다. 문제를 읽으면서도 '이 정도 문제는 바로 풀이가 나와야지'라고 생각했을 정도로. 쉬운 문제들을 풀어보며 그리디 알고리즘에 어느 정도 익숙해져야겠다 생각했었는데, 효과가 나타나는 모양이다. (사실 익숙해지고 말고의 문제를 떠나서 문제 난이도 자체가 낮은 것이라고는 하지만...)