백준 1900 - 레슬러 (자바 - 그리디)

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

1900번: 레슬러

 

* 문제 요약

레슬링 선수들은 초자연적인 힘을 가졌다. 경기에 이기기 위해 레슬링 선수는 자신의 힘 뿐만 아니라 경기할때 착용하는 마술 링에도 의존한다. 마술 링은 레슬링 선수로 하여금 상대 선수의 힘에 비례하는 힘을 추가로 얻을 수 있게 해준다.

레슬링 선수의 힘과 마술 링의 힘은 모두 양의 정수이다. 선수 A 가 선수 B 와 경기할 때, A 의 경기력은 A 의 힘 + (B의 힘 * A 가 착용하고 있는 마술 링의 힘) 이다. 경기에서는 경기력이 높은 선수가 이긴다.

 

예를 들어 선수 A의 힘이 10이고 착용하고 있는 마술 링의 힘은 3 이라고 하고, 선수 B의 힘은 18이고 착용하고 있는 마술 링의 힘은 4라고 하자.

이 두 선수가 경기를 가지면 A 가 이긴다. 왜냐하면 A의 경기력은 10 + (3 * 18) = 64 이지만 B의 경기력은 18 + (4 * 10) = 58 이기 때문이다.

만약 A 가 힘이 15이고 마술의 힘이 5인 링을 착용한 선수 C 를 만났다면 C 가 이긴다.

이 경기에서 A 의 경기력은 10 + (3 * 15) = 55 이고, C의 경기력은 15 + (5 * 10) = 65 이다.

마찬가지로 B와 C의 경기에서는 C가 이긴다.

 

매년 레슬링 축제에서 축제기간에 레슬링 선수는 다른 모든 선수들과 한번씩 경기를 가진다. 이 축제의 마지막엔 레슬링 선수를 모두 초대하여 축하하고 금화를 수여한다.

이때 수여되는 금화의 수는 해당 선수가 이긴 경기수와 선수들의 줄에서 어느 위치에 서 있느냐로 결정된다.

한 선수가 받는 금화의 갯수는 그가 이긴 경기 수 + 선수들의 줄에서 자기보다 앞에 있는데 자기가 이긴 선수의 수이다.

 

예를 들어 위의 세 선수 A, B, C 에게 A, B, C 의 순서로 금화를 나눠주게 되면 A 는 금화 1개, B 는 금화 0개, C 는 4개를 받게 된다. C는 2경기를 이겨서 2개에, 자기가 이긴 A, B 가 자기보다 줄에서 앞에 있으므로 각각 하나씩 2개를 합하여 총 4개를 받는다.

만약 C, A, B 순서라면 C는 2개, A는 1개, B는 0개를 받게된다.

 

이때, 재정을 고려하여 수여하는 금화의 수를 최소화 하고자 한다. 우리가 할 일은 수여하는 금화의 수를 최소화 하도록 선수들이 줄을 서는 순서를 결정하는 것이다.

모든 선수들의 힘과 가진 마술 링의 힘이 주어진다. 경기에서 비기는 경우를 발생시키지 않는다고 가정한다.

 

* 입력

첫째 줄에 선수들의 수 N 이 주어진다. 선수들은 1부터 N까지 번호가 붙어있다.

다음 N개의 줄에는 한 줄에 한 선수의 힘과 그가 가진 마술 링의 힘이 주어진다.

선수 k의 정보는 k + 1 번째 줄에 주어진다.

N은 10,000 이하이고, 선수의 힘과 마술 링의 힘은 모두 1이상 1,000 이하라고 가정하여도 좋다.

 

* 출력

수여되는 금화를 최소화 할 수 있도록 선수들을 줄 세웠을 때 한 줄에 하나씩 순서대로 선수의 번호를 출력한다.

 

* 예시

 

* 해결 과정

수여되는 금화를 최소화 하려면 경기에서 승리한 횟수가 많은 선수들부터 내림차순으로 정렬하여 줄을 세워주는 것이 좋다.

금화가 수여되는 조건이 승리한 경기 횟수 + 자신보다 앞에 있는 사람 중 자신이 승리한 사람 숫자인데, 여기서 경기를 승리한 횟수는 입력값이 그대로 활용되어 책정되기 때문에 함부로 변화시킬 수 없으나, 자신보다 앞에 있는 사람들의 숫자는 줄을 세우는 과정에서 원하는대로 변경시킬 수 있다.

여기서 승리한 경기수가 많은 사람을 최대한 줄 앞에 세워주면 그만큼 그 선수의 앞에 서 있는 선수들의 숫자가 줄어드므로 자연스럽게 앞에 서 있는 사람들 중 자신이 승리한 사람의 숫자를 최소화 시킬 수 있게된다.

 

각 선수당 승리한 횟수는 매 반복마다 탐색을 통해 현재 탐색하고 있는 선수를 기준으로 그 뒤에 있는 선수들에 대해서만 경기력을 계산하여 누가 이겼는지 확인하고 이긴 선수의 승리횟수를 올려주는 방식으로 횟수를 계산해주면 된다.

왜냐하면 다음 탐색으로 그 뒤에 있는 선수를 기준으로 승리한 횟수를 확인할 때, 자신의 앞에서 먼저 탐색했던 선수들을 대상으로는 이미 경기력을 비교하여 승패를 결정한 상태이므로 굳이 자신의 앞에 존재하는 선수들에 대해서 다시 한번 경기력을 계산하여 승패를 확인해줄 필요가 없기 때문이다.

 

* 코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int arraySize = Integer.parseInt(br.readLine());
        Player[] playerArray = new Player[arraySize];

        int inputCount = 1;
        for(int i = 0; i < arraySize; i++){
            String[] inputArray = br.readLine().split(" ");
            int power = Integer.parseInt(inputArray[0]);
            int ring = Integer.parseInt(inputArray[1]);

            Player player = new Player(power, ring, inputCount, 0);
            inputCount++;
            playerArray[i] = player;
        }

        for(int i = 0; i < arraySize-1; i++){

            Player player = playerArray[i];

            // 앞전에 비교한 선수들 끼리는 굳이 또 비교해주고 있을 필요 없음
            for(int j = i+1; j < arraySize; j++){
                
                // 각 인덱스 별로 승패 확인 데이터 저장
                Player compareP = playerArray[j];

                int playerA = player.power + (player.ring * compareP.power);
                int playerB = compareP.power + (compareP.ring * player.power);

                if(playerA > playerB) {
                    player.win = player.win + 1;
                    playerArray[i] = player;
                }
                else if(playerA < playerB){
                    compareP.win = compareP.win + 1;
                    playerArray[j] = compareP;
                }
            }
        }

        Arrays.sort(playerArray);

        for(int i = 0; i < playerArray.length; i++){
            bw.write(playerArray[i].inputCount + "\n");
        }

        bw.flush();
        bw.close();
        br.close();

    }
}

class Player implements Comparable<Player>{
    int power;
    int ring;

    int win;
    int inputCount;

    public Player(int power, int ring, int inputCount, int win){
        this.power = power;
        this.ring = ring;
        this.inputCount = inputCount;
        this.win = win;
    }

    // 정렬이 내림차순으로 되게끔 메소드 내용 작성
    @Override
    public int compareTo(Player o) {
        return o.win - this.win;
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 금화 수여갯수를 최소화 하기 위해 승리가 가장 많은 선수들부터 먼저 줄을 세워준다.

선택한 해답이 조건을 만족하는지 검사한다. -> 줄을 세운 모든 선수들에게 금화가 수여되기 전까지는 금화가 최소로 수여된 상태인지 알 수 없으므로, 승리가 가장 많은 선수들부터 순서대로 계속 줄을 세워가며 끝까지 출력해준다.

 

위의 과정을 통해 금화를 최소로 수여하는데 최대한 가까운 방식으로 선수들을 줄 세웠으므로 그리디 알고리즘에 해당된다.