프로그래머스 Level2 이모티콘 할인행사 (Java)

• https://school.programmers.co.kr/learn/courses/30/lessons/150368
• 문제
  • n개의 이모티콘을 할인하여 판매한다.
  • 각 유저는 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 전부 구매한다.
  • 각 유저는 이모티콘 구매 비용의 합이 자신의 기준보다 크다면 모든 구매를 취소하고 이모티콘 플러스 서비스에 가입한다.
  • 이모티콘마다 할인율은 다를 수 있다.
    • 이모티콘의 할인율은 10%,20%,30%,40% 중 하나다.
  • 카카오톡의 목표는 다음과 같다.
    1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
    2. 이모티콘 판매액을 최대한 늘리는 것.
  • 1번목표가 우선이며, 2번목표가 그 다음이다.
  • 행사목적을 최대로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 반환하시오.
• 제한사항
  • 1 ≤ users의 길이 = n ≤ 100
    • users의 원소는 [비율, 가격]의 형태입니다.
    • users[i]는 i+1번 고객의 구매 기준을 의미합니다.
    • 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
      • 1 ≤ 비율 ≤ 40
    • 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
      • 100 ≤ 가격 ≤ 1,000,000
      • 가격은 100의 배수입니다.
  • 1 ≤ emoticons의 길이 = m ≤ 7
    • emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
    • 100 ≤ emoticons의 원소 ≤ 1,000,000
    • emoticons의 원소는 100의 배수입니다.
• 코드

public class Solution {
	private static int[] answer = {0,0};
	private static int[] discounts;
	private static int maxDiscount = 10;
	private static int minDiscount = 40;
	private static void dfs(int depth,int[] discount,int[][] users, int[] emoticons) {
		if(depth == emoticons.length) {
			int user = 0;
			int cost = 0;
			for(int i = 0; i < users.length; i++) {
				int curCost = 0;
				for(int j = 0; j < emoticons.length; j++) {
					if(users[i][0] <= discount[j]) {
						curCost += emoticons[j]*(100-discount[j])/100;
					}
				}
				if(users[i][1] <= curCost) {
					user++;
				}else {
					cost+=curCost;
				}
			}
			if(user > answer[0]) {
				answer[0] = user;
				answer[1] = cost;
			}else if(user == answer[0] && cost > answer[1]) {
				answer[1] = cost;
			}
			return;
		}
		for(int i = 0; i < discounts.length; i++) {
			discount[depth] = discounts[i];
			dfs(depth+1,discount,users,emoticons);
		}
	}
	
    public int[] solution(int[][] users, int[] emoticons) {
    	for(int i = 0; i < users.length; i++) {
    		int cur = ((int)Math.ceil(users[i][0]/10.0))*10;
    		if(cur < minDiscount) {
    			minDiscount = cur;
    		}
    		
    		if(cur > maxDiscount) {
    			maxDiscount = cur;
    		}
    	}
    	
    	discounts = new int[(maxDiscount-minDiscount)/10+1];
    	int cur = minDiscount;
    	for(int i = 0; i < discounts.length; i++) {
    		discounts[i] = cur;
    		cur+=10;
    	}
    	dfs(0,new int[emoticons.length],users,emoticons);
        return answer;
    }
}

• 풀이
  • 완전탐색문제다. user의 수 (할인율의 수)^(이모티콘의 길이)를 하면 길어야 1004^7로 대략 160만정도의 경우의 수가 나온다. 즉 모든 경우의 수를 탐색하면 된다.
  • 주의해야 할 점은 모든 이모티콘은 같아도 되고, 달라도 되기 때문에 중복순열을 구해야 한다는 것이다.