2023 KAKAO BLIND RECRUITMENT-이모티콘 할인행사-C++

이모티콘 할인행사 문제 바로가기

이번문제는 간단히 BT를 사용하여 완전탐색을 하면 된다.

왜 BackTracking으로 사용해야 했을까?

처음에 문제를 접했을때? 퍼뮤테이션을 사용하여 순열과 조합을 사용해야 하나 ? 싶었다.

그런데 순열은 말이 안되는게
4개의 숫자 1,2,3,4중에서 순열은
1,2,3,4
1,2,4,3,
1,3,2,4
.,..
등등 이런식이지
1,1,1,1
1,1,1,2
1,1,1,3
이런식으로 나오지 않았다.

즉 이모티콘이 1000,2000,3000,40000원으로 있다면
우리는 할인률을 완전탐색으로
10,10,10,10,
10,10,10,20,
10,10,10,30
10,10,10,40
10,10,20,10
10,10,20,20,
,,,
이런식으로 전부 살펴봐야 한다.

실제로 이렇게 해도 될까?
검증부터 해야한다.
이모티콘의 갯수는 최대 7개이다
그럼 4^7이라는건데 1억번이 안넘으니까 괜찮다.

그러면 어떻게 BackTracking을 구성할까?

void A(int c){
    for(int i=0;i<4;i++){
        v.push_back(d[i]);
        c++;
        if(c<cnt){
            A(c);
        }else{
            check();
        }
        c--;
        v.pop_back();
    }
}

일단 for문을 4번 돈다 무조건
왜냐면 할인률은 4개로 정해져 있기 때문이다.
그래서 v에다가 넣고 c++을 한다.
c++이란 이모티콘의 갯수이다. 즉
c가 0에서 1로 변했다는건
첫번쨰 원소
10 이 되었다는것이다.
cnt는 이모티콘 size인 4이다.

그러면 v에 10이들어가있는 상태로 for문을 다시 돌고
그러면 c가 2가 되고 v는 10 10 이 될것이다.

이런식으로 쭉가다가 10 10 10 10 이면 check로 검사를 하고
c--로 빼주고
v.pop_back으로 마지막 원소를 빼준다.
그러면 다음에 push할때는 10 10 10 20 이 들어가게된다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int cnt = 0;
vector<int> d;
vector<int> v;
vector<vector<int>> u;
vector<int> e;

int maxuser=0;
int maxprice=0;

//현재 v에 이모티콘은 [1300, 1500, 1600, 4900] [10,10,20,30]들어있음
void check(){
    int adduser=0;
    int addprice=0;
    for(int i=0;i<u.size();i++){
        int uprate = u[i][0];
        int upprice = u[i][1];
        int price = 0;
        for(int j=0;j<v.size();j++){
            if(uprate<=v[j]){
                price += (e[j] * (100-v[j]))/100;
            }
        }
        if(price>=upprice){
            adduser++;
        }else{
            addprice += price;
        }
    }
    if(adduser>maxuser){
        maxuser = adduser;
        maxprice = addprice;
    }else if(adduser==maxuser && addprice>maxprice){
        maxuser = adduser;
        maxprice = addprice;
    }
}

void A(int c){
    for(int i=0;i<4;i++){
        v.push_back(d[i]);
        c++;
        if(c<cnt){
            A(c);
        }else{
            check();
        }
        c--;
        v.pop_back();
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    u=users;
    e=emoticons;
    vector<int> answer;
    cnt=emoticons.size();
    d.push_back(10);
    d.push_back(20);
    d.push_back(30);
    d.push_back(40);
    A(0);
    answer.push_back(maxuser);
    answer.push_back(maxprice);
    return answer;
}

다른코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int e_size=0;
vector<int> answer;
int d[4]={10,20,30,40};
vector<vector<int>> users;
vector<int> emoticons;
void cal(vector <int> &v){
    int plus = 0;
    int T_A =0;
    for(int i=0;i<users.size();i++){
        int rate = users[i][0];
        int amount = users[i][1];
        int tmp = 0;
        for(int j=0;j<v.size();j++){
            if(rate <=v[j]){
                tmp +=(emoticons[j]*(100-v[j]))/100;
            }
        }
        if(amount <= tmp){
            plus++;
        }else{
            T_A += tmp;
        }
    }
    if(plus>answer[0]){
        answer[0]=plus;
        answer[1]=T_A;
    }else if(plus == answer[0] && T_A > answer[1]){
        answer[1]=T_A;
    }
}

void discount_combi(vector<int>&v){
    if(v.size()==e_size){
        cal(v);
        return;
    }
    
    for(int i=0;i<4;i++){
        v.push_back(d[i]);
        discount_combi(v);
        v.pop_back();
    }
}


vector<int> solution(vector<vector<int>> userss, vector<int> emoticonss) {
    emoticons = emoticonss;
    users=userss;
    answer.push_back(0);
    answer.push_back(0);
    e_size=emoticons.size();
    vector<int>v;
    discount_combi(v);
    return answer;
}