[Programmers] 이모티콘 할인행사(LV.2)

풀이 소요시간 : 40분

실수 없이 단번에 구현에 성공했다. 이런 비문학 지문같은 구현문제는 문제 읽으면서 멘탈 잘 관리하고, 정밀하게 코드 짜기만하면 풀 수 있는 경우가 잦은듯하다. 카카오 기출은 처음 풀어봤다.

구현 문제에 별다른 알고리즘을 넣는 경우는 없는 듯 하다. 해봤자 탐색, 백 트래킹 정도를 요구한다.

접근 방식

전역변수화를 진행하면서 가격 조합 생성 방식을 고민했다. 백 트래킹 방식이 유일하다고 생각하여 Dfs() 으로 구현했다.

가격 조합 하나를 완성할 때 마다 Make_Result() 함수를 작동시켜 결과 가입자, 매출액 값을 저장시켰다.

마지막으로 순차 정렬시킨 마지막 값을 정답으로 제출했다.

전체 코드

참고로 나는 구조체 사용을 아주 좋아한다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct User {
    int Sale;
    int Max;
};

struct Emo {    
    int Price;
};


vector<User> User_Vector;
vector<Emo> Emo_Vector;


int S[4] = {10, 20, 30, 40};
vector<int> Sale_Vector;
vector<pair<int ,int>> Result_Vector;
//가입자 수, 가격

void Make_Result() {

    int Total_Sum = 0;
    int Sign = 0;

    //모든 회원 대상 검사
    for(int i = 0; i < User_Vector.size(); i++) {

        int Sale = User_Vector[i].Sale;
        int Max = User_Vector[i].Max;

        int Sum = 0;

        //회원의 기준치에 부합한 이모티콘 가격의 합산이 이루어진다.
        for(int j = 0; j < Sale_Vector.size(); j++) {

            if(Sale_Vector[j] < Sale) continue;
            int New_Price = ( Emo_Vector[j].Price * (100 - Sale_Vector[j]) ) / 100;
            Sum += New_Price;

        }

        //합산 완료
        if(Sum >= Max) {
            //이모티콘 가입
            Sign++;
        }
        else {
            //이모티콘 구매
            Total_Sum += Sum;
        }

    }

    Result_Vector.push_back({Sign, Total_Sum});
    //최종 가입자 수, 매출액 결과 저장
}


void Dfs(int Count) {

    //모든 이모티콘의 할인율이 결정되면
    if(Count == Emo_Vector.size()) {
        Make_Result();
        return;
    }

    //백 트래킹 -> [10, 10, 10, 10] ~ [40, 40, 40, 40] 의 모든 조합 생성
    for(int i = 0; i < 4; i++) {
        Sale_Vector.push_back(S[i]);
        Dfs(Count + 1);
        Sale_Vector.pop_back();
    }

}



vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {

    for(int i = 0; i < users.size(); i++) {
        int Sale = users[i][0];
        int Max = users[i][1];
        User_Vector.push_back({Sale, Max});
    }

    for(int i = 0; i < emoticons.size(); i++) {
        int Price = emoticons[i];
        Emo_Vector.push_back({Price});
    }
    // 전역변수 세팅

    Dfs(0);
    // 조합 생성하기

    sort(Result_Vector.begin(), Result_Vector.end());
    int Ans_Sign = Result_Vector[Result_Vector.size() - 1].first;
    int Ans_Total = Result_Vector[Result_Vector.size() - 1].second;

    return {Ans_Sign, Ans_Total};

}