[알고리즘] 2023 Kakao Blind 이모티콘 할인행사 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/150368

프로그래머스

 

프로그래머스 기준 난이도 lv2로 선정된 카카오 블라인드 채용 코테문제였다.

 

이전 문제였던 이모티콘 할인 행사 문제처럼 딱히 어려울 부분은 없었던 문제였다고 생각한다.

 

m의 값이 최대 7이기 때문에 최대 4^7번이므로 충분히 탐색할 수 있어 dfs를 사용했다.

 

class Solution {
    int cnt,max;
    static int discount[];
    public void dfs(int[][] users, int emoticons[], int size,int depth){
        if(depth == size){
            int buy = 0;
            int pay = 0;
            for(int i=0;i<users.size;i++){
                int sum=0;
                for(int j=0;j<size;j++){
                    if(users[i][0]<=discount[j]*10){
                        sum+=(int)emoticons[j]*(10-discount[j])*10/100;
                    }
                }
                
                if(users[i][1]<=sum){
                    buy++;
                }
                else{
                    pay+=sum;
                }
            }
            
            
            if(cnt<buy){
                cnt = buy;
                max = pay;
            }
            else if(cnt==buy && max<pay){
                max=pay;
            }            
            return;
        }
        
        for(int i=1;i<=4;i++){
            discount[depth]=i;
            dfs(users,emoticons,size,depth+1);
        }
    }
    
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = new int[2];
        
        //discount의 값 = 1~4의 값(10%할인~40%할인 의미)
        discount = new int[emoticons.length];
        
        cnt=0;
        max=0;
        
        dfs(users,emoticons,emoticons.length,0);
        
        answer[0] = cnt;
        answer[1] = max;
        
        return answer;
    }
}