[프로그래머스 C#] Lv.2 이모티콘 할인행사

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 우선순위(서비스 가입, 매출)에 따라 가장 좋은 성과를 낼 수 있는 경우를 구하는 문제

 

- 할인율은 10%, 20%, 30%, 40%로 고정

 -> 중복 연산을 최소화하기 위해 각 이모티콘의 할인율을 미리 연산해둠 (costArrays)

 

- 이모티콘의 최대 개수는 7개, 유저의 최대 인원은 100명 : 이모티콘을 기준으로 해야 함

 -> 이모티콘들의 각 할인율이 변화하는 모든 경우의 수를 체크 ( DFS 알고리즘 )

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

 

- 할인율에 따른 모든 경우의 수에 대해 유저의 서비스 가입 여부와 매출액을 확인 및 answer 갱신

 ( 단, 서비스에 가입한 사람은 매출액을 합산하지 않아야 함 )

 

주석 참조

    using System;

    public class Solution
    {
        public int[] solution(int[,] users, int[] emoticons)
        {
            int[] answer = new int[2] { 0, 0 };

            // [상품 인덱스, 할인율/10] = 할인된 가격
            var costArrays = new int[emoticons.Length, 5];

            // 할인율에 따른 값 미리 세팅
            for (int i = 0; i < emoticons.Length; i++)
                for (int j = 1; j <= 4; j++)
                    costArrays[i, j] = emoticons[i] - (emoticons[i] / 10) * j;

            var currArray = new int[emoticons.Length]; // 적용할 할인율 배열
            DFS(0, currArray, users, costArrays, ref answer);

            return answer;
        }

        public void DFS(int currIndex, int[] currArray, int[,] users, int[,] costArrays, ref int[] answer)
        {
            // 모든 할인율 세팅
            if (currIndex < currArray.Length)
            {
                // 할인율 세팅 ( 10, 20, 30, 40% )
                for (int i = 1; i <= 4; i++)
                {
                    currArray[currIndex] = i;
                    DFS(currIndex + 1, currArray, users, costArrays, ref answer);
                }
                return;
            }

            // 할인율에 따른 서비스 가입자 수, 매출액 측정
            int totalCost = 0; // 매출액
            int totalCount = 0; // 서비스 가입자 수
            for (int i = 0; i < users.GetLength(0); i++)
            {
                int userCost = 0;
                
                // 구매할 이모티콘 체크
                for (int j = 0; j < currArray.Length; j++)
                    if (currArray[j] * 10 >= users[i, 0])
                        userCost += costArrays[j, currArray[j]];

                // 서비스 가입 조건 충족 체크
                if (userCost >= users[i, 1])
                    totalCount++;
                else
                    totalCost += userCost;
            }

            // 우선순위가 앞서는 데이터 발견 시 answer 갱신
            if (answer[0] < totalCount)
            {
                answer[0] = totalCount;
                answer[1] = totalCost;
            }
            else if (answer[0] == totalCount && answer[1] < totalCost)
            {
                answer[1] = totalCost;
            }
        }
    }