[Coding Test] 이모티콘 할인행사/c#

 

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

프로그래머스

문제 요약

목표

• 이모티콘 플러스 서비스 가입자 수 최대화 (우선조건)
• 이모티콘 매출액 최대화
• 출력: [가입자 수, 총 매출액]

조건

• n명의 사용자, m개의 이모티콘
• 이모티콘 할인률: 10%, 20%, 30%, 40% (이모티콘별로 다르게 적용가능)
• 사용자
  • 비율 기준 이상 할인 → 이모티콘 구매
  • 구매 금액 총 합 >= 기준 금액 → 이모티콘 구매 취소 후 서비스 가입

입출력 예

입력

int[,] users = new int[,] { {40, 10000}, {25, 10000} };
int[] emoticons = new int[] { 7000, 9000 };

 

출력

[1, 5400]

 

풀이 전략

1. 모든 할인율 조합 탐색

각 이모티콘마다 4가지 할인율 → 조합 수 = 4^m
m ≤ 7이므로 최대 16,384조합으로 완전 탐색 가능
DFS 재귀로 구현

2. 사용자 구매 시뮬레이션

사용자별

1. 기준 할인율 이상인 이모티콘 구매
2. 총 구매액이 기준 금액 이상 → 서비스 가입
3. 그렇지 않으면 구매 금액 합산

 

가입자 수 > 매출액 우선순위로 최적값 갱신

 

C# 구현

using System;

public class Solution {
    int maxJoin = 0;
    int maxSales = 0;

    public int[] solution(int[,] users, int[] emoticons)
    {
        dfs(0, users, emoticons, new int[emoticons.Length]);
        int[] answer = new int[] { maxJoin, maxSales };
        return answer;
    }

    private void dfs(int index, int [,] user, int[] emoticons, int[] discounts)
    {
        if (index == emoticons.Length)
        {
            Simulate(discounts, emoticons, user);
            return;
        }

        int[] possibleDiscounts = new int[] { 10, 20, 30, 40 };

        foreach (var discount in possibleDiscounts)
        {
            discounts[index] = discount;
            dfs(index + 1, user, emoticons, discounts);
        }
    }

    private void Simulate(int[] discounts, int[] emoticons, int[,] users)
    {
        int joinCount = 0;
        int sales = 0;
        int n = users.GetLength(0);

        for (int i = 0; i < n; i++)
        {
            int userDiscount = users[i, 0];
            int userThreshold = users[i, 1];
            int totalPrice = 0;

            for (int j = 0; j < emoticons.Length; j++)
            {
                if (discounts[j] >= userDiscount)
                {
                    totalPrice += emoticons[j] * (100 - discounts[j]) / 100;
                }
            }

            if (totalPrice >= userThreshold)
            {
                joinCount++;
            }
            else
            {
                sales += totalPrice;
            }
        }

        if (joinCount > maxJoin)
        {
            maxJoin = joinCount;
            maxSales = sales;
        }
        else if (joinCount == maxJoin)
        {
            maxSales = Math.Max(maxSales, sales);
        }
    }
}