1. 문제설명

이모티콘 플러스 서비스 가입자 수를 늘리려고 한다.
서비스 가입자 수를 최대한 늘렸다면, 판매액을 최대한 늘리려고 한다.
n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매한다.
할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정된다.
카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입한다.
- 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘 모두 구매
- 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입

2. 입/출력

입력
- 카카오톡 사용자 n명
- n명의 구매 기준을 담은 2차원 정수 배열 users
- 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons
출력
- 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return

3. 문제 분류

Simulation, DFS

4. 알고리즘 설계

이모티콘의 할인율은 사용자 모두에게 똑같이 적용된다.
- 10%부터 40%까지 담은 배열을 이용해 DFS를 수행하면 된다.
```
for (int i = 0; i < 4; i++) {
  	discnt.push_back(dc[i]);
  	dfs(discnt);
  	discnt.pop_back();
  }
```
최대 매출액을 찾기 위해서는 할인율의 조합을 전부 시도해보는 수밖에 없다.
- discnt의 크기가 emoticons의 크기와 같아지면 계산할 준비가 된 것이다.
서비스 가입 여부와 구입 금액 계산
- 이모티콘을 순차적으로 하나씩 꺼낸다.
- 만약 할인율이 사용자가 지정한 할인율(users의 값)보다 적다면 건너뛴다.
- 그렇지 않다면 할인된 금액의 합을 계산한다.
  - cost * (100 - dis) / 100
  - 여기서 ids는 DFS에서 수행된 임시 할인율이다.
- 계산을 하던 중 할인된 금액의 합이 사용자의 구매 금액 이상이 되면 {1, 0}을 리턴한다.
  - 구독을 하게 되었다는 뜻이다.
- 구매 금액 미만이면 {0, 금액의 합}을 리턴한다.
  - 구독없이 이모티콘을 구입했다는 뜻이다.
위와 같은 방식으로 모든 사용자의 구매 기준에 따른 구독 여부와 계산 금액 각각을 전부 합친다.
구독의 수가 더 많다면 또는 구독의 수는 같은데 금액의 합이 더 크다면 값을 갱신한다.

5. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int dc[] = { 10, 20, 30, 40 };
vector<int> EMOTICONS;
vector<vector<int>> USERS;
int subscribe, sales;

pii calc(int idx, vector<int> discnt) {
	pii ret;

	int lim_dc = USERS[idx][0];
	int lim_cost = USERS[idx][1];
	int sum_cost = 0;

	for (int i = 0; i < EMOTICONS.size(); i++) {
		int cost = EMOTICONS[i];
		int dis = discnt[i];
		if (dis < lim_dc) continue;

		sum_cost += cost * (100 - dis) / 100;

		if (sum_cost >= lim_cost) {
			ret.first = 1;
			ret.second = 0;
			return ret;
		}
	}

	ret.second = sum_cost;
	return ret;
}

void dfs(vector<int> discnt) {
	if (discnt.size() == EMOTICONS.size()) {
		pii cmp = { 0,0 };

		for (int i = 0; i < USERS.size(); i++) {
			auto res = calc(i, discnt);
			cmp.first += res.first;
			cmp.second += res.second;
		}

		if (cmp.first > subscribe) {
			subscribe = cmp.first;
			sales = cmp.second;
		}
		else if (cmp.first == subscribe && cmp.second > sales)
			sales = cmp.second;

		return;
	}

	for (int i = 0; i < 4; i++) {
		discnt.push_back(dc[i]);
		dfs(discnt);
		discnt.pop_back();
	}
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
	USERS.assign(users.begin(), users.end());
	EMOTICONS.assign(emoticons.begin(), emoticons.end());

	dfs({});

	return {subscribe, sales};
}

6. 소감

개인의 할인율과 현재 조합의 할인율 등을 구분하기 위해 이름이 약간 다른 변수명을 지었다.
- 이것 때문에 문제를 풀면서 너무 헷갈렸다.
- 문제가 어려운 게 아니라 변수 이름 때문에..
users와 emoticons를 대문자로 변수명을 지어 전역으로 선언해 복사했다.
- 물론 DFS 함수에 전달할 수도 있다.
- 그러나, 문제 내에서는 참조만 할 뿐 수정을 하지 않기 때문에
- 재귀마다 값을 복사하는 게 비효율적이라고 느껴졌다.

Programmers. 이모티콘 할인행사

1. 문제설명

2. 입/출력

3. 문제 분류

4. 알고리즘 설계

5. 전체 코드

6. 소감