[C++] Programmers: 이모티콘 할인행사

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 프로그래머스 레벨 2으로, DFS로 해결하려 하였을 때에는 해결책이 도저히 보이지 않아 풀지 못할 것으로 예상하였으나 DFS를 포기하고 백트래킹을 활용하여 문제를 풀 수 있었다.

문제 링크

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

문제 분석

문제를 풀기 위해서 수업 시간에는 힌트로 DFS가 주어졌으나, 필자는 DFS를 사용하는 대신 백트래킹을 통해 문제를 해결하였다. 백트래킹을 활용하여 이모티콘의 할인도의 경우의 수를 모두 찾아내 문제를 해결할 수 있었다.

문제 풀이

문제를 풀 때에 백트래킹을 적극적으로 활용하였다.

void backtracing(int depth)
{
// ...
    for (int i = 1; i <= 4; i++)
    {
        emoticonSales.push_back(i * 10);
        backtracking(depth + 1);
        emoticonSales.pop_back();
    }
}

위에 작성한 코드와 같이 함수명을 백트래킹으로 지정하고, 내부적으로 이모티콘의 할인도의 경우의 수를 모두 생성하도록 구현하였다. backtracking 함수의 인자로 전달되는 건 실제로는 더 많지만, 지금은 읽기 편하게 하기 위해 depth만 표현하였다. 만약 판매하는 이모티콘이 4개라면, 백트래킹을 통해 [10, 10, 10, 10], [10, 10, 10, 20]... [40, 40, 40, 40]과 같이 모든 할인율의 경우의 수를 생성하게 된다. 참고로 백트래킹을 구현할 때에는 재귀를 활용하였다.

void backtracing(int depth)
{
    if (depth == emoticonSize)
    {
        int currentEmoticonPlusUserNumber = answer[0];
        int currentEmoticonProfit = answer[1];

        int newEmoticonPlusUserNumber = 0;
        int newEmoticonProfit = 0;
        int userSize = userList.size();
        vector<int> newEmoticonProfits(userSize, 0);
        for (int i = 0; i < userSize; i++)
        {
            for (int j = 0; j < emoticonSize; j++)
            {
                if (userList[i][0] <= emoticonSales[j])
                {
                    newEmoticonProfits[i] += emoticonList[j] * double(100 - emoticonSales[j]) / double(100);
                }
                if (newEmoticonProfits[i] >= userList[i][1])
                {
                    newEmoticonPlusUserNumber += 1;
                    newEmoticonProfits[i] = 0;
                    break;
                }
            }
            newEmoticonProfit += newEmoticonProfits[i];
        }

        if (currentEmoticonPlusUserNumber < newEmoticonPlusUserNumber)
        {
            answer[0] = newEmoticonPlusUserNumber;
            answer[1] = newEmoticonProfit;
        }
        else if (currentEmoticonPlusUserNumber == newEmoticonPlusUserNumber && newEmoticonProfit > currentEmoticonProfit)
        {
            answer[1] = newEmoticonProfit;
        }
        return;
    }
    // ...
}

백트래킹 함수의 depth가 emoticon의 갯수와 같아진다면, 즉 [40, 40, 40, 40]과 같이 모든 할인율의 경우의 수가 생성되었다면 문제에서 주어진 이모티콘 플러스 서비스 가입자를 최대한 늘리면서, 이모티콘 판매액 또한 최대로 늘리는 경우의 답을 계산한다.

전체 코드

전체 코드는 다음과 같다. 위에서 함수의 파라미터를 간단히 작성한 것과 달리 함수의 파라미터가 많다.

#include <string>
#include <vector>

using namespace std;

void backtracking(int depth, vector<vector<int>> &userList, vector<int> &emoticonList, vector<int> &emoticonSales, vector<int> &answer)
{
    int emoticonSize = emoticonList.size();
    if (depth == emoticonSize)
    {
        int currentEmoticonPlusUserNumber = answer[0];
        int currentEmoticonProfit = answer[1];

        int newEmoticonPlusUserNumber = 0;
        int newEmoticonProfit = 0;
        int userSize = userList.size();
        vector<int> newEmoticonProfits(userSize, 0);
        for (int i = 0; i < userSize; i++)
        {
            for (int j = 0; j < emoticonSize; j++)
            {
                if (userList[i][0] <= emoticonSales[j])
                {
                    newEmoticonProfits[i] += emoticonList[j] * double(100 - emoticonSales[j]) / double(100);
                }
                if (newEmoticonProfits[i] >= userList[i][1])
                {
                    newEmoticonPlusUserNumber += 1;
                    newEmoticonProfits[i] = 0;
                    break;
                }
            }
            newEmoticonProfit += newEmoticonProfits[i];
        }

        if (currentEmoticonPlusUserNumber < newEmoticonPlusUserNumber)
        {
            answer[0] = newEmoticonPlusUserNumber;
            answer[1] = newEmoticonProfit;
        }
        else if (currentEmoticonPlusUserNumber == newEmoticonPlusUserNumber && newEmoticonProfit > currentEmoticonProfit)
        {
            answer[1] = newEmoticonProfit;
        }
        return;
    }
    for (int i = 1; i <= 4; i++)
    {
        emoticonSales.push_back(i * 10);
        backtracking(depth + 1, userList, emoticonList, emoticonSales, answer);
        emoticonSales.pop_back();
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons)
{
    vector<int> emoticonSales;
    vector<int> answer(2, 0);
    backtracking(0, users, emoticons, emoticonSales, answer);

    return answer;
}