문제링크

문제 링크

문제 설명

제한사항

입출력 예

입출력 예 설명은 링크 참조 ㅎㅎ

풀이

1. 어디 문제 제한사항에서 배열의 길이가 한자리 수 제한으로 주어진다..? 그러면 최소 재귀를 이용한 완전탐색을 생각해야하는것같다.
2. 이 문제는 각 상품마다 10 ~ 40까지 할인율 모두 적용해보고 각 할인율 적용됐으면, 유저 배열 돌려서 구매 로직을 구현하면 된다.
3. 그럼 각 상품별 할인율 적용할 수 있는 경우의 수는, 4의 emoticons.length만큼 제곱한 값이 되는데, 이게 최대 길이가 7까지 주어지기때문에 4를 7번 곱한게 16000번 조금 더 넘는다..
4. 아 참고로 나는 [10, 20, 30, 40] 배열을 이모티콘 개수만큼 선언해서 0 1 2 3되는 인덱스들을 재귀로 돌렸다.
5. 아 참고로 이 문제는 가격 단위 모두가 100의 배수로만 선언되기때문에, double형 타입이 필요한가?에 대한 고민은 필요가 없다

처음에 백트래킹으로 풀려고 메소드 명을 dfs로 선언하긴했는데

그 부분은 넘어가주길 바람..ㅎ

코드

import java.util.*;
class Solution {
    static int[][] discounts;
    static int[] answer;
    static boolean[] visited;
    static int[] index;
    public void init(int N) {
        int dc = 40;
        discounts = new int[4][N];
        visited = new boolean[N];
        index = new int[N + 1];        
        for(int i = 0; i < 4; i++, dc -= 10)
            for(int j = 0; j < N; j++)
                discounts[i][j] = dc;

        for(int i = 0; i < index.length; i++)
            index[i] = 0;
    }
    public void dfs(int[][] users, int[] emoticons,int start, int N) {
        if(start == N) {
            //계산
            int join = 0; //answer[0]
            int sell = 0; //answer[1]
            int sum = 0;
            for(int i = 0; i < users.length; i++) {
                sum = 0;
                for(int j = 0; j < N; j++) {
                //System.out.println(emoticons[j] + "의 "+discounts[index[j]][j]+"%할인 후 가격 = " + price);
                    if(users[i][0] <= discounts[index[j]][j]) { //생각했던 할인율 보다 높으면 일단 삼
                        int price = emoticons[j] - emoticons[j] * discounts[index[j]][j] / 100;
                        sum += price;
                    }
                }
                if(sum >= users[i][1])
                    join++;
                else
                    sell += sum;
            }
            if(join > answer[0]) {
                answer[0] = join;
                answer[1] = sell;
            }
            else if(join == answer[0] && answer[1] < sell)
                answer[1] = sell;
            return ;
        }
        
        for(int i = 0; i < 4; index[start]++,i++) {
            index[start + 1] = 0;
            dfs(users, emoticons, start + 1, N);
        }
    }
    public int[] solution(int[][] users, int[] emoticons) {
        answer = new int[2];
        init(emoticons.length); //초기화
        dfs(users,emoticons, 0, emoticons.length);
        
        return answer;
    }
}