[프로그래머스] C# 2023 KAKAO BLIND RECRUITMENT 이모티콘 할인행사 Lv 2 / DFS

2023 KAKAO BLIND RECRUITMENT 이모티콘 할인행사 Lv 2

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

프로그래머스

---

DFS를 이용한 접근을 공부중이라 사용해보았다. 모든 경우를 탐색하면 된다

머릿속에서 정리가 필요해서 그림판을 그려가며 정리했고,, 

이모티콘이 5가지 (A, B, C, D, E), 할인 방법은 4가지(10%, 20%, 30%, 40%) 라고 한다면

A가 10%, 20%, 30%, 40%일 때 각각 B도 10, 20, 30, 40 이런식의 경우를 모두 내려가면서 구해야했고, 이를 구현해보았다.

 

Test 함수가 DFS 함수이고, 제일 마지막단계에 도달했을 때 계산을 때리고 계산 한 후 최대의 이득을 보는걸 저장하는 코드이다.

using System;

public class Solution {
    public int[] solution(int[,] users, int[] emoticons) {
        int[] answer = new int[2];
        int[] sales = new int[] {10, 20, 30, 40};
        
        int[] emoticonSales = new int[emoticons.Length]; 
        
        for (int i = 0; i < sales.Length; i++){
            Test(sales, 0, i, emoticons, emoticonSales, users, answer); // 이모티콘 A의 할인 = sales[i];
        }
        
        return answer;
    }
    
    private void Test(int[] sales, int depth, int index, int[] emoticons, int[] emoticonSales, int[,] users, int[] answer){
        emoticonSales[depth] = sales[index];
        if (depth == emoticons.Length-1){
            Calculate(users, emoticons, emoticonSales, answer);
            return;
        }
        for (int i = 0; i< sales.Length; i++){
            Test(sales, depth+1, i, emoticons, emoticonSales, users, answer);
        }
    }
    
    private void Calculate(int[,] users, int[] emoticons, int[] emoticonSales, int[] answer){
        int services = 0; //서비스 가입한 사람들
        int total = 0; //총 구매 비용
        
        for (int i = 0; i < users.GetLength(0); i++){ //users 한명씩 반복
            int price = 0;
            for (int j = 0; j < emoticons.Length; j++){ //이모티콘 검사
                if (users[i, 0] <= emoticonSales[j] ) { //할인율이 크다면
                    price += emoticons[j] * (100 - emoticonSales[j]) / 100;
                }
            }
            if (users[i, 1] <= price){ //소유한 돈보다 구매하려는게 더 많다면
                price = 0;
                services++;
            }
            else {total += price;}
        }
        
        if (answer[0] < services){
            answer[0] = services;
            answer[1] = total;
        }
        else if (answer[0] == services && answer[1] < total){
            answer[1] = total;
        }
    }
}