ํ๋ก๊ทธ๋๋จธ์ค ์ด๋ชจํฐ์ฝ ํ ์ธํ์ฌ ํ์ด
๋ฌธ์ ์ค๋ช
์นด์นด์คํก์์๋ ์ด๋ชจํฐ์ฝ์ ๋ฌด์ ํ์ผ๋ก ์ฌ์ฉํ ์ ์๋ ์ด๋ชจํฐ์ฝ ํ๋ฌ์ค ์๋น์ค ๊ฐ์ ์ ์๋ฅผ ๋๋ฆฌ๋ ค๊ณ ํฉ๋๋ค.
์ด๋ฅผ ์ํด ์นด์นด์คํก์์๋ ์ด๋ชจํฐ์ฝ ํ ์ธ ํ์ฌ๋ฅผ ํ๋๋ฐ, ๋ชฉํ๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- ์ด๋ชจํฐ์ฝ ํ๋ฌ์ค ์๋น์ค ๊ฐ์ ์๋ฅผ ์ต๋ํ ๋๋ฆฌ๋ ๊ฒ.
- ์ด๋ชจํฐ์ฝ ํ๋งค์ก์ ์ต๋ํ ๋๋ฆฌ๋ ๊ฒ.
**1๋ฒ ๋ชฉํ๊ฐ ์ฐ์ ์ด๋ฉฐ, 2๋ฒ ๋ชฉํ๊ฐ ๊ทธ ๋ค์์ ๋๋ค.**
์ด๋ชจํฐ์ฝ ํ ์ธ ํ์ฌ๋ ๋ค์๊ณผ ๊ฐ์ ๋ฐฉ์์ผ๋ก ์งํ๋ฉ๋๋ค.
n
๋ช ์ ์นด์นด์คํก ์ฌ์ฉ์๋ค์๊ฒ ์ด๋ชจํฐ์ฝยm
๊ฐ๋ฅผ ํ ์ธํ์ฌ ํ๋งคํฉ๋๋ค.- ์ด๋ชจํฐ์ฝ๋ง๋ค ํ ์ธ์จ์ ๋ค๋ฅผ ์ ์์ผ๋ฉฐ, ํ ์ธ์จ์ 10%, 20%, 30%, 40% ์ค ํ๋๋ก ์ค์ ๋ฉ๋๋ค.
์นด์นด์คํก ์ฌ์ฉ์๋ค์ ๋ค์๊ณผ ๊ฐ์ ๊ธฐ์ค์ ๋ฐ๋ผ ์ด๋ชจํฐ์ฝ์ ์ฌ๊ฑฐ๋, ์ด๋ชจํฐ์ฝ ํ๋ฌ์ค ์๋น์ค์ ๊ฐ์ ํฉ๋๋ค.
- ๊ฐ ์ฌ์ฉ์๋ค์ ์์ ์ ๊ธฐ์ค์ ๋ฐ๋ผ ์ผ์ ๋น์จ ์ด์ ํ ์ธํ๋ ์ด๋ชจํฐ์ฝ์ ๋ชจ๋ ๊ตฌ๋งคํฉ๋๋ค.
- ๊ฐ ์ฌ์ฉ์๋ค์ ์์ ์ ๊ธฐ์ค์ ๋ฐ๋ผ ์ด๋ชจํฐ์ฝ ๊ตฌ๋งค ๋น์ฉ์ ํฉ์ด ์ผ์ ๊ฐ๊ฒฉ ์ด์์ด ๋๋ค๋ฉด, ์ด๋ชจํฐ์ฝ ๊ตฌ๋งค๋ฅผ ๋ชจ๋ ์ทจ์ํ๊ณ ์ด๋ชจํฐ์ฝ ํ๋ฌ์ค ์๋น์ค์ ๊ฐ์ ํฉ๋๋ค.
๋ถ์
๊ฐ ์ด๋ชจํฐ์ฝ์ ํ ์ธ์จ์ 4๊ฐ์ง๋ก ๊ฒฐ์ ๋๋ค. (๋๋ ๊ผญ ํ ์ธํ๋ค๋ ๋ง์ด ์๋ ์ค์๊ณ 0%๊น์ง ๊ณ์ฐํด ์ด 5๊ฐ์ง๋ก ๊ณ์ฐํ๋ค.) ์ด๋ชจํฐ์ฝ์ ์ต๋7๊ฐ์ด๋ฉฐ, ๊ฒฝ์ฐ์์๋ $4^7$, $2^{14}$ ์ด๋ฏ๋ก ์ฝ 16,000 ์ด๋ฏ๋ก ์์ ํ์์ ์งํํด๋ ๋๋ํ๊ฒ ๊ตฌํํ ์ ์๋ค.
ํด๊ฒฐ๊ณผ์
์์ ํ์์ผ๋ก ๊ตฌํ์ ์งํํจ.
- dfs๋ก ๊ตฌํํ์ฌ, ์ธ๋ฑ์ค๋ฅผ ํ๋์ฉ ๋์(๊ฐ ์ด๋ชจํฐ์ฝ์ 10 ~ 40%์ ํ ์ธ์จ์ ์ ํ)
- ๋ชจ๋ ์ด๋ชจํฐ์ฝ์ ํ ์ธ์จ์ด ๊ฒฐ์ ๋๋ฉด(dfs ํ์ถ ์กฐ๊ฑด) ๊ฐ ์ ์ ๋ฅผ ์ํํ๋ฉฐ, ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์ ์ ์ ํ๋งค์ก์ ๊ณ์ฐํ์ฌ ์ ๋ต๊ณผ ๋น๊ตํ๋ค.
์์ค์ฝ๋
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
int sales[5] = {0, 10,20, 30,40};
using namespace std;
int check[7];
int max_size;
vector<int> ans;
void dp(int idx, vector<vector<int>> users, vector<int> emoticons){
if(idx == max_size){
int cnt = 0;
int total = 0;
for(vector<int> user : users){
int sum = 0;
int sale = user[0];
int price = user[1];
for(int i = 0; i<max_size; i++){
if(check[i] >= sale){
sum += emoticons[i] * (100 - check[i])/100;
}
}
if(sum >= price) cnt++;
else total += sum;
}
if(ans[0] < cnt){
ans[0] = cnt;
ans[1] = total;
}
else if(ans[0] == cnt && ans[1] < total){
ans[0] = cnt;
ans[1] = total;
}
return;
}
for(int i = 0; i<5; i++){
check[idx] = sales[i];
dp(idx + 1, users, emoticons);
}
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
ans.resize(2);
max_size = emoticons.size();
dp(-1, users, emoticons);
return ans;
}
๋ฐฐ์ด์
๋ฌธ์ ๊ผผ๊ผผํ๊ฒ ๋ณด์..!