반응형
문제: 마력
이 문제는 PriorityQueue를 활용하면 쉽게 풀 수 있다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.PriorityQueue; | |
import java.util.Scanner; | |
public class Main { | |
private PriorityQueue mPQ; | |
private int mUseItem; | |
public Main(int numItem,int useItem){ | |
mPQ=new PriorityQueue(); | |
mUseItem=useItem; | |
} | |
public void addItem(int itemPower){ | |
//PriorityQueue 가 Order하는 순서를 거꾸로 하도록 음수로 처리 | |
mPQ.add(-itemPower); | |
} | |
public void calculate(){ | |
int power=0; | |
int itempower=0; | |
for(int i=0;i<mUseItem;i++){ | |
//아이템이 더이상 없으면 마력을 출력하고 종료 | |
//시도 횟수가 아이템 수보다 많을 수 있음 | |
if(mPQ.isEmpty()){ | |
System.out.println(power); | |
return; | |
} | |
//음수로 가장 큰 값 추출 | |
itempower=(int)mPQ.remove(); | |
//마력에 더함(음수니까 뻄) | |
power=power-itempower; | |
//아이템의 마력이 다 떨이지지 않았다면 | |
if(itempower<=-1) { | |
//아이템 마력을 하나 감소시키고 | |
itempower++; | |
//아이템을 다시 추가 | |
mPQ.add(itempower); | |
} | |
} | |
System.out.println(power); | |
} | |
public static void main(String[] args) { | |
Scanner sc=new Scanner(System.in); | |
int caseCnt=sc.nextInt(); | |
for(int caseIdx=0;caseIdx<caseCnt;caseIdx++){ | |
int numItem=sc.nextInt(); | |
int useItem=sc.nextInt(); | |
Main solution=new Main(numItem,useItem); | |
for(int i=0;i<numItem;i++){ | |
solution.addItem(sc.nextInt()); | |
} | |
solution.calculate(); | |
} | |
} | |
} |
반응형