문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=cpp
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이모티콘의 개수가 7개로 한정적이고 할인율의 종류도 5가지이므로 백트래킹으로 쉽게 풀 수 있는 문제였습니다. (제가 계산했을 때는 시간복잡도가 O(5^7 * 100)였습니다.)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |

개발환경: Programmers IDE
지적, 조언, 질문 환영합니다! 질문 남겨주세요~
반응형
'알고리즘 > programmers' 카테고리의 다른 글
[Programmers] 대여 횟수가 많은 자동차들의 월별 대여 횟수 구하기 (3) | 2023.01.15 |
---|---|
[Programmers] 자동차 대여 기록 별 대여 금액 구하기 (0) | 2023.01.13 |
[Programmers] 오프라인/온라인 판매 데이터 통합하기 (0) | 2023.01.11 |
[Programmers] 택배 배달과 수거하기 (0) | 2023.01.10 |
[Programmers] 주문량이 많은 아이스크림들 조회하기 (0) | 2023.01.09 |