[Programmers] 이모티콘 할인행사

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

프로그래머스

 

이모티콘의 개수가 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

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