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

문제 링크

---

프로그래머스

접근 방법

---

각 이모티콘은 10%, 20%, 30%, 40% 중 하나의 할인율을 가질 수 있습니다.
이모티콘의 개수가 최대 7개이므로 가능한 할인 조합의 수는 최대 4^7 = 16,384개입니다.
따라서 모든 할인율 조합을 dfs로 확인해도 충분히 해결할 수 있습니다.

소스 코드

---

class Solution {

    int maxSum = 0, maxPlusUser = 0;
    int[] userSum;

    void recursive(int idx, int[][] users, int[] emoticons) {
        if (emoticons.length == idx) {
            int sum = 0, plusUser = 0;
            for (int i = 0; i < users.length; i++) {
                if (users[i][1] <= userSum[i]) {
                    plusUser++;
                } else {
                    sum += userSum[i];
                }
            }

            if (maxPlusUser < plusUser) {
                maxPlusUser = plusUser;
                maxSum = sum;
            } else if (maxPlusUser == plusUser && sum > maxSum) {
                maxSum = sum;
            }

            return;
        }

        for (int i = 90; i > 50; i -= 10) {
            for (int j = 0; j < users.length; j++) {
                if (users[j][0] >= i) {
                    userSum[j] += emoticons[idx] * i;
                }
            }

            recursive(idx + 1, users, emoticons);

            for (int j = 0; j < users.length; j++) {
                if (users[j][0] >= i) {
                    userSum[j] -= emoticons[idx] * i;
                }
            }
        }
    }

    public int[] solution(int[][] users, int[] emoticons) {
        userSum = new int[users.length];

        for (int i = 0; i < users.length; i++) {
            users[i][0] = 100 - users[i][0];
        }

        for (int i = 0 ; i < emoticons.length; i++) {
            emoticons[i] /= 100;
        }

        recursive(0, users, emoticons);
        return new int[]{maxPlusUser, maxSum};
    }
}

코드 설명

---

maxPlusUser는 현재까지 찾은 최대 이모티콘 플러스 가입자 수를 저장합니다.
maxSum은 가입자 수가 같을 때 비교할 최대 판매액을 저장합니다.
userSum은 현재 할인율 조합에서 각 유저가 구매한 이모티콘 금액의 합을 저장합니다.

 

먼저 유저의 기준 할인율을 결제 비율 기준으로 변환합니다.
예를 들어 기준 할인율이 40%라면 100 - 40 = 60으로 바꿉니다.
이 값은 정가의 60% 이하로 구매할 수 있는 경우, 즉 40% 이상 할인되는 경우에만 구매한다는 의미입니다.

이모티콘 가격은 모두 100의 배수이므로 미리 100으로 나눕니다.
이렇게 하면 재귀 내부에서 emoticons[idx] * i / 100처럼 매번 나누기 연산을 하지 않고, emoticons[idx] * i만으로 할인가를 계산할 수 있습니다.

 

recursive()는 현재 idx번째 이모티콘의 할인 후 결제 비율을 선택합니다.
반복문에서 i는 90, 80, 70, 60으로 변하며, 각각 10%, 20%, 30%, 40% 할인을 의미합니다.

각 유저에 대해 users[j][0] >= i이면 해당 이모티콘을 구매합니다.
예를 들어 유저 기준 할인율이 25%라면 변환 후 값은 75입니다.
현재 할인율이 30%라면 결제 비율은 70이므로 75 >= 70이 되어 구매합니다.
현재 할인율이 20%라면 결제 비율은 80이므로 75 >= 80이 거짓이 되어 구매하지 않습니다.

재귀 호출 전에는 현재 이모티콘 구매 금액을 userSum에 더합니다.
재귀 호출이 끝난 뒤에는 같은 값을 다시 빼서 이전 상태로 되돌립니다.