참고
문제해설
문제 로직고민
NOTE
•
사실 처음에는 문제보고 내가 모르는 알고리즘인줄 알고 당황했는데 제한사항을 보니 브루트포스 문제였다.
◦
판매하는 이모티콘은 최대 7개이다.
◦
할인하는 비율은 10, 20, 30, 40 4개중 하나이다.
•
브루트포스로 모든 할인의 경우를 계산해서 이모티콘 플러스를 가장 많이 가입시키면서 많이 판매하는 경우를 뽑는다.
작성코드
NOTE
import java.util.*;
class Solution {
int[][] users;
int[] emoticons;
int[] sales;
int[] av_sales = {10, 20, 30, 40};
PriorityQueue<int[]> answer;
public int[] solution(int[][] users, int[] emoticons) {
this.users = users;
this.emoticons = emoticons;
this.sales = new int[emoticons.length];
answer = new PriorityQueue<int[]>((a1, a2) -> {
if(a1[0] == a2[0]) return a2[1] - a1[1];
else return a2[0] - a1[0];
});
dfs(0);
int[] a = answer.poll();
return a;
}
private void dfs(int cnt){
if(cnt == emoticons.length){
int emoticon_plus = 0;
int total_money = 0;
for(int[] user : users){
int money = 0;
for(int i=0; i< sales.length; i++){
if(sales[i] < user[0]) continue;
money += emoticons[i] / 100 * (100 - sales[i]);
}
if(money >= user[1]) emoticon_plus++;
else total_money += money;
}
answer.offer(new int[]{emoticon_plus, total_money});
return;
}
for(int i=0; i<4; i++){
sales[cnt] = av_sales[i];
dfs(cnt+1);
}
}
}
Java
복사