Post

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ด๋ชจํ‹ฐ์ฝ˜ ํ• ์ธํ–‰์‚ฌ ํ’€์ด

๋ฌธ์ œ์„ค๋ช…

์นด์นด์˜คํ†ก์—์„œ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜์„ ๋ฌด์ œํ•œ์œผ๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜ ํ”Œ๋Ÿฌ์Šค ์„œ๋น„์Šค ๊ฐ€์ž…์ž ์ˆ˜๋ฅผ ๋Š˜๋ฆฌ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

์ด๋ฅผ ์œ„ํ•ด ์นด์นด์˜คํ†ก์—์„œ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜ ํ• ์ธ ํ–‰์‚ฌ๋ฅผ ํ•˜๋Š”๋ฐ, ๋ชฉํ‘œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  1. ์ด๋ชจํ‹ฐ์ฝ˜ ํ”Œ๋Ÿฌ์Šค ์„œ๋น„์Šค ๊ฐ€์ž…์ž๋ฅผ ์ตœ๋Œ€ํ•œ ๋Š˜๋ฆฌ๋Š” ๊ฒƒ.
  2. ์ด๋ชจํ‹ฐ์ฝ˜ ํŒ๋งค์•ก์„ ์ตœ๋Œ€ํ•œ ๋Š˜๋ฆฌ๋Š” ๊ฒƒ.

**1๋ฒˆ ๋ชฉํ‘œ๊ฐ€ ์šฐ์„ ์ด๋ฉฐ, 2๋ฒˆ ๋ชฉํ‘œ๊ฐ€ ๊ทธ ๋‹ค์Œ์ž…๋‹ˆ๋‹ค.**

์ด๋ชจํ‹ฐ์ฝ˜ ํ• ์ธ ํ–‰์‚ฌ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ์ง„ํ–‰๋ฉ๋‹ˆ๋‹ค.

  • n๋ช…์˜ ์นด์นด์˜คํ†ก ์‚ฌ์šฉ์ž๋“ค์—๊ฒŒ ์ด๋ชจํ‹ฐ์ฝ˜ย m๊ฐœ๋ฅผ ํ• ์ธํ•˜์—ฌ ํŒ๋งคํ•ฉ๋‹ˆ๋‹ค.
  • ์ด๋ชจํ‹ฐ์ฝ˜๋งˆ๋‹ค ํ• ์ธ์œจ์€ ๋‹ค๋ฅผ ์ˆ˜ ์žˆ์œผ๋ฉฐ, ํ• ์ธ์œจ์€ 10%, 20%, 30%, 40% ์ค‘ ํ•˜๋‚˜๋กœ ์„ค์ •๋ฉ๋‹ˆ๋‹ค.

์นด์นด์˜คํ†ก ์‚ฌ์šฉ์ž๋“ค์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ธฐ์ค€์„ ๋”ฐ๋ผ ์ด๋ชจํ‹ฐ์ฝ˜์„ ์‚ฌ๊ฑฐ๋‚˜, ์ด๋ชจํ‹ฐ์ฝ˜ ํ”Œ๋Ÿฌ์Šค ์„œ๋น„์Šค์— ๊ฐ€์ž…ํ•ฉ๋‹ˆ๋‹ค.

  • ๊ฐ ์‚ฌ์šฉ์ž๋“ค์€ ์ž์‹ ์˜ ๊ธฐ์ค€์— ๋”ฐ๋ผ ์ผ์ • ๋น„์œจ ์ด์ƒ ํ• ์ธํ•˜๋Š” ์ด๋ชจํ‹ฐ์ฝ˜์„ ๋ชจ๋‘ ๊ตฌ๋งคํ•ฉ๋‹ˆ๋‹ค.
  • ๊ฐ ์‚ฌ์šฉ์ž๋“ค์€ ์ž์‹ ์˜ ๊ธฐ์ค€์— ๋”ฐ๋ผ ์ด๋ชจํ‹ฐ์ฝ˜ ๊ตฌ๋งค ๋น„์šฉ์˜ ํ•ฉ์ด ์ผ์ • ๊ฐ€๊ฒฉ ์ด์ƒ์ด ๋œ๋‹ค๋ฉด, ์ด๋ชจํ‹ฐ์ฝ˜ ๊ตฌ๋งค๋ฅผ ๋ชจ๋‘ ์ทจ์†Œํ•˜๊ณ  ์ด๋ชจํ‹ฐ์ฝ˜ ํ”Œ๋Ÿฌ์Šค ์„œ๋น„์Šค์— ๊ฐ€์ž…ํ•ฉ๋‹ˆ๋‹ค.

๋ถ„์„

๊ฐ ์ด๋ชจํ‹ฐ์ฝ˜์˜ ํ• ์ธ์œจ์€ 4๊ฐ€์ง€๋กœ ๊ฒฐ์ •๋œ๋‹ค. (๋‚˜๋Š” ๊ผญ ํ• ์ธํ•œ๋‹ค๋Š” ๋ง์ด ์—†๋Š” ์ค„์•Œ๊ณ  0%๊นŒ์ง€ ๊ณ„์‚ฐํ•ด ์ด 5๊ฐ€์ง€๋กœ ๊ณ„์‚ฐํ–ˆ๋‹ค.) ์ด๋ชจํ‹ฐ์ฝ˜์€ ์ตœ๋Œ€7๊ฐœ์ด๋ฉฐ, ๊ฒฝ์šฐ์˜์ˆ˜๋Š” $4^7$, $2^{14}$ ์ด๋ฏ€๋กœ ์•ฝ 16,000 ์ด๋ฏ€๋กœ ์™„์ „ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•ด๋„ ๋„‰๋„‰ํ•˜๊ฒŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

ํ•ด๊ฒฐ๊ณผ์ •

์™„์ „ํƒ์ƒ‰์œผ๋กœ ๊ตฌํ˜„์„ ์ง„ํ–‰ํ•จ.

  1. dfs๋กœ ๊ตฌํ˜„ํ•˜์—ฌ, ์ธ๋ฑ์Šค๋ฅผ ํ•˜๋‚˜์”ฉ ๋†’์ž„(๊ฐ ์ด๋ชจํ‹ฐ์ฝ˜์€ 10 ~ 40%์˜ ํ• ์ธ์œจ์„ ์„ ํƒ)
  2. ๋ชจ๋“  ์ด๋ชจํ‹ฐ์ฝ˜์˜ ํ• ์ธ์œจ์ด ๊ฒฐ์ •๋˜๋ฉด(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;
}

๋ฐฐ์šด์ 

๋ฌธ์ œ ๊ผผ๊ผผํ•˜๊ฒŒ ๋ณด์ž..!

This post is licensed under CC BY 4.0 by the author.