[완전탐색] - Lv2 - 2023 KAKAO BLIND RECRUITMENT - 이모티콘 할인 행사

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

프로그래머스

 

🌿 - 문제 설명

 

📌- 풀이

 

 

처음 문제를 읽고 예시를 봤을 때 문제 이해를 잘 못해서 시간이 오래걸렸다.

 

- 처음 이해한 내용은 1번 조건에서 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구해합니다.

 

이 부분에서 할인하는 이모티콘'만' 구매한다고 생각했어야 됐는데, 할인 하는 이모티콘도 모두 구매하고 할인 안 하는 이모티콘도 구매 했을 때의 비용으로 플러스 가입 유무를 판단한다고 착각했다.

예를 들어 1,2번 이모티콘이 모두 10퍼센트만 할인한다고 했을 때 -> 안산다라는 결론이 나와야하는데 둘다 산다라는 생각을 해서 둘다 사면 만원이 넘으니까 구독자가 2명이 늘겠네? 이렇게 잘못 생각했다.

 

책을 많이 읽자..

 

 

어쨌든 제대로 이해하고 다시 문제를 보니 경우의 수도 이모티콘의 수가 7개이고 10~40%까지 총 4개로 4^7의 경우의 수가 나와서 약 16000번 정도의 연산이기 때문에 완전탐색을 이용해서 풀면 되겠다고 생각해서 문제를 풀었다.

 

 

 

이런 식으로 각각의 할인율을 바탕으로 전체적으로 탐색을 해주면 문제를 풀 수 있다.

 

 

🔥 - Java 전체 코드

 

class Solution {
        static int[] discount ={10,20,30,40};
        static int userLength,emoticonLength,maxSub,maxCost;
        
        
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = {};
        userLength = users.length;
        emoticonLength = emoticons.length;
        int[] disDFS = new int[emoticonLength];
    
        backDFS(0,emoticonLength,users,emoticons,disDFS);
        return new int[]{maxSub,maxCost};
        
    }
    
    public void backDFS(int index, int emoticonLength, int[][] users, int[] emoticons, int[] disDFS)      { 
        if(index == emoticonLength){ // emoticon 할인율 배열이 가득 찼을 때 - ex) [10,10] ~ [40,40] 까지의 할인율 
            int sub = 0 ;
            int cos = 0 ;
            
            for(int[] user : users){
                
                int userPer = user[0]; 
                int userCos = user[1];
                
                int sum=0;
                
                for(int i =0;i<emoticonLength;i++){
                    if(disDFS[i]>=userPer){ // 유저의 구매 할인율보다 배열안의 할인율이 높거나 같을 때 구매하기 위해
                        sum += (emoticons[i] * (100- disDFS[i])) / 100;
                    }
                }
                if(sum >= userCos){ // 유저의 구매 가격이 한계 가격보다 높을 때 구독하기 위해서
                    sub++;
                }else{
                    cos+=sum;
                }
                
            }
            if(maxSub<=sub){ // 구독자수가 같거나 높을 때 cost 변경
                if(maxSub<sub){
                    maxCost = cos; // 구독자수가 더 높을 때는 무조건 최대 cost이므로
                }else{
                    maxCost=Math.max(maxCost,cos);  // 구독자 수가 같을 때는 최고 비용
                }
                maxSub=sub;       
            }
            return;
            
        }else{
            for(int i=0;i<4;i++){ // 재귀로 탐색하기 위해
                disDFS[index] = discount[i]; // 할인율 세팅
                backDFS(index+1, emoticonLength, users,emoticons,disDFS);
            }
        }
    }
    
}