[프로그래머스] 이모티콘 할인행사

[문제풀이]

할인율은 총 4가지(10%, 20%, 30%, 40%)이며 이모티콘의 최대 갯수는 7개이므로 4^7이므로 중복조합을 이용하여 완전탐색으로 풀었습니다.
문제 설명에서
1.이모티콘 플러스 서비스 가입자를 최대한 늘리는 것. 2.이모티콘 판매액을 최대한 늘리는 것. 1번 목표가 우선이며, 2번 목표가 그 다음입니다.
라고 주어졌으므로 할인율이 클 수록 구매하는 이모티콘의 수가 많아져서 이모티콘 플러스 서비스 가입자를 최대한 늘릴 수 있으므로 할인율이 가장 높은 40%부터 선택하여 탐색하도록 문제를 풀어나갔습니다.

[코드]

class Solution {
    static int maxPrice, maxJoin;
  static int[] discount_data = {40, 30, 20, 10};
  public static int[] solution(int[][] users, int[] emoticons) {
    int[] answer = new int[2];
    int[] discount = new int[emoticons.length];


    // 이모티콘 할인율 구하기
    dfs(emoticons.length, 0, users, emoticons, discount);

    answer[0] = maxJoin;
    answer[1] = maxPrice;
    return answer;
  }

  private static void dfs(int len, int cnt, int[][] users, int[] emoticon ,int[] discount) {
    if(cnt == len){
      int salesPrice = 0;
      int cntSubscriber = 0;

      for(int[] user: users){
        int userdiscount = user[0];
        int userPrice = user[1];

        int tempPrice = 0;

        for(int i=0; i<discount.length; i++){
          //사용자의 요구 할인율보다 현재 할인율이 더 클 때
          if(userdiscount <= discount[i]){
              tempPrice += emoticon[i]* (100-discount[i]) / 100;
          }
        }

        if(tempPrice >= userPrice) cntSubscriber++;
        else salesPrice += tempPrice;
      }

      if(maxJoin < cntSubscriber){
        maxJoin = cntSubscriber;
        maxPrice = salesPrice;

      } else if (maxJoin == cntSubscriber){
        maxPrice = Math.max(maxPrice, salesPrice);
      }

      return;
    }
    
    //중복조합
    for(int i=0; i<4; i++){
      discount[cnt] = discount_data[i];
      dfs(len, cnt+1, users, emoticon, discount);
    }
  }
}