2023 카카오 블라인드 채용 이모티콘 행사 c++ (브루트 포스)

 

 

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

프로그래머스

 

제한 사항에서 이모티콘은 최대 8개, 할인의 종류는 4개이다. 8개 이모티콘에 대한 모든 할인의 경우의 수는 

4*4*....*4 = 4^8 만큼의 경우의 수를 구하면 된다.

이 4개의 할인 경우의 수를 0,1,2,3 이라는 캐릭터에 담아서, 8자리 문자열에 저장하는 것으로 경우의 수를 표현했다.

ex) 01010101 -> 1째 == 10%,2째 == 20%,....8째 == 20% 

dfs를 통해 가능한 모든 문자열을 생성한 뒤, 모든 경우의 수에 대해 총 이익, 구독자 수를 구하면서 최대 구독자, 최대 이익을 찾으면 된다.

 

#include <string>
#include <vector>

using namespace std;
vector<vector<int>> all;
int saleArr[4]={10,20,30,40};
int siz=0;
void make_posibility(vector<int> v){
    if(v.size()==siz){
            all.push_back(v);
            return;
    }
    for(int i=0;i<4;i++){
        v.push_back(i);
        make_posibility(v); 
        v.pop_back();
    }
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer;
    siz=emoticons.size();
    vector<int> tmp;
    make_posibility(tmp);
    int max_sub=-1,max_total=-1;
    for(int p=0;p<all.size();p++){//확률 가짓수
        vector<int> sale=all[p];
        int sub=0, total=0;
        for(int i=0;i<users.size();i++){//각 유저가 해당 세일 상황에서 행동
            int my_sum=0,my_sale=users[i][0],max=users[i][1];
            for(int s=0;s<siz;s++){
                int saleNum=saleArr[sale[s]];
                if(saleNum<my_sale) continue;
                int sale_price=(emoticons[s]/100)*(100-saleNum);
                my_sum+=sale_price;  
                if(my_sum>=max){ //예산 초과 시 모두 취소 후 구독
                    my_sum=0;
                    sub++;
                    break;   
                }
            }
            total+=my_sum;
        } 
        if(max_sub<sub){
            max_sub=sub;
            max_total=total;
        }
        if(max_sub==sub&&max_total<total) max_total=total;    
    }
    answer.push_back(max_sub);
    answer.push_back(max_total);
    return answer;
}