알고리즘/programmers

[Programmers] 이모티콘 할인행사

꾸준함. 2023. 1. 11. 14:29

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=cpp 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

이모티콘의 개수가 7개로 한정적이고 할인율의 종류도 5가지이므로 백트래킹으로 쉽게 풀 수 있는 문제였습니다. (제가 계산했을 때는 시간복잡도가 O(5^7 * 100)였습니다.)

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int maxEmoticonPlus = 0;
int maxSales = 0;
void calculate(vector<int> &salesRates, vector<vector<int>> &users, vector<int> &emoticons)
{
int emoticonPlus = 0;
int sales = 0;
for (vector<int> user : users)
{
int temp = 0;
for (int i = 0; i < salesRates.size(); i++)
{
if (user[0] > salesRates[i])
{
continue;
}
temp += (emoticons[i] / 100) * (100 - salesRates[i]);
}
if (temp >= user[1])
{
emoticonPlus++;
}
else
{
sales += temp;
}
}
if (maxEmoticonPlus > emoticonPlus)
{
return;
}
if (maxEmoticonPlus == emoticonPlus
&& maxSales >= sales)
{
return;
}
maxEmoticonPlus = emoticonPlus;
maxSales = sales;
}
void func(vector<int> salesRates, vector<vector<int>> &users, vector<int> &emoticons)
{
if (salesRates.size() == emoticons.size())
{
calculate(salesRates, users, emoticons);
return;
}
for (int i = 10; i <= 40; i += 10)
{
salesRates.push_back(i);
func(salesRates, users, emoticons);
salesRates.pop_back();
}
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
vector<int> v;
func(v, users, emoticons);
vector<int> answer;
answer.push_back(maxEmoticonPlus);
answer.push_back(maxSales);
return answer;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

 

반응형