[๋ฐฑ์ค€/C++] 5021๋ฒˆ ์™•์œ„๊ณ„์Šน

2022. 7. 18. 18:47ยทPS/C++
๋ฐ˜์‘ํ˜•

๋ฐฑ์ค€
๋ฐฑ์ค€
5021๋ฒˆ ์™•์œ„๊ณ„์Šน
5021๋ฒˆ ์™•์œ„๊ณ„์Šน


๐Ÿค”๋ฌธ์ œ ์ดํ•ด

๋‚˜๋ผ๋ฅผ ์„ธ์šด ์‚ฌ๋žŒ์ด 1 ์™•์กฑ์ด๊ณ , ์™•์กฑ์ด ์•„๋‹Œ ์™ธ๋ถ€ ์‚ฌ๋žŒ์€ 0์™•์กฑ์ด๋‹ค.

๋ถ€๋ชจ์˜ ์™•์กฑ ์ ์ˆ˜๋ฅผ ๊ฐ๊ฐ 2๋กœ ๋‚˜๋ˆ„์–ด ๋”ํ•œ ๊ฐ’์ด ์ž์‹์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ๋˜๊ณ , ์™•์œ„๋ฅผ ๊ณ„์Šน๋ฐ›๊ธฐ๋ฅผ ์ฃผ์žฅํ•˜๋Š” ์‚ฌ๋žŒ๋“ค ์ค‘ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋†’์€ ์‚ฌ๋žŒ์„ ์ถœ๋ ฅํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ด๋‹ค.


๐Ÿ’ก์ฒซ๋ฒˆ์งธ ์•„์ด๋””์–ด

์˜ˆ์ œ ์ž…๋ ฅ

9 2
edwardi
charlesi edwardi diana
philip charlesi mistress
wilhelm mary philip
matthew wilhelm helen
edwardii charlesi laura
alice laura charlesi
helen alice bernard
henrii edwardii roxane
charlesii elizabeth henrii
charlesii
matthew

์˜ˆ์ œ ์ž…๋ ฅ1์„ ๋ฐ”ํƒ•์œผ๋กœ ์ง  ๊ฐ€๊ณ„๋„์ด๋‹ค. helen๊ณผ wilhelm์˜ ์ž์‹ matthew์˜ ๊ด€๊ณ„๊ฐ€ ์ž…๋ ฅ์—์„œ ๋จผ์ € ๋‚˜์˜ค์ง€๋งŒ ๊ฒฐ๊ณผ์ ์œผ๋กœ helen ๋˜ํ•œ ์™•์กฑ์ด ๋˜๋ฏ€๋กœ ์ž…๋ ฅ ์ค‘๊ฐ„์— ๊ณ„์‚ฐ์€ ๋ถˆ๊ฐ€๋Šฅํ•ด ๋ณด์˜€๋‹ค.

 

๊ทธ๋ž˜์„œ ์ผ๋‹จ ์ž์‹ ์ด๋ฆ„์„ key๋กœ ํ•˜๊ณ  ๋ถ€๋ชจ ์ด๋ฆ„๊ณผ ์™•์กฑ ์ ์ˆ˜๋ฅผ value๋กœ ๊ฐ–๋Š” map ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์‚ฌ์šฉํ•ด

์ž์‹-๋ถ€๋ชจ ๊ด€๊ณ„๋ฅผ ์ €์žฅํ•ด๋†“๊ณ  ํ˜„์žฌ ์ž์‹์— ๋Œ€ํ•ด ๊ทธ ๋ถ€๋ชจ์— ๋Œ€ํ•ด ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋‚˜๋ˆ„์–ด ์ƒ๊ฐํ•ด๋ณด์•˜๋‹ค.

1. ๋ถ€๋ชจ ํ•œ์ชฝ๋งŒ ์™•์กฑ

  1-1. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ(0์ด ์•„๋‹Œ ๊ฒฝ์šฐ)

  1-2. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ (0์ธ ๊ฒฝ์šฐ)

2. ๋ถ€๋ชจ ์–‘์ชฝ ๋‹ค ์™•์กฑ

  2-1. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ๋‘˜๋‹ค ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ

  2-2. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์™ผ์ชฝ ๋ถ€๋ชจ๋งŒ ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ

  2-3. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์˜ค๋ฅธ์ชฝ ๋ถ€๋ชจ๋งŒ ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ

  2-4. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ๋‘˜๋‹ค ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ

 

๋ถ€๋ชจ-์ž์‹ ๊ด€๊ณ„๋ฅผ ์•Œ๋ ค์ฃผ๋Š” ์ž…๋ ฅ๊ฐ’๋“ค์€ ๋”ฐ๋กœ ๋ฐฐ์—ด์— ์ €์žฅํ•ด๋†“๊ณ  ์ฒซ ์ž…๋ ฅ์€ ๋‚˜๋ผ๋ฅผ ์„ธ์šด ์™•๊ณผ ๊ทธ์˜ ๋ฐฐ์šฐ์ž, ๊ทธ์˜ ์ž์‹ ๊ด€๊ณ„์ด๋ฏ€๋กœ ๊ฐ€์žฅ ์ฒ˜์Œ ์ž…๋ ฅ๊ฐ’๋ถ€ํ„ฐ ์ž์‹์˜ ์™•์กฑ ์ ์ˆ˜๋ฅผ ์ฐพ์•„์คฌ๋‹ค.

while๋ฌธ ์•ˆ์—์„œ ๋ชจ๋“  ์ž…๋ ฅ๊ฐ’๋งŒํผ for๋ฌธ์„ ๋Œ๋ฉด์„œ ๊ทธ ๋ถ€๋ชจ๊ฐ€ ์™•์กฑ์ธ๋ฐ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด ๊ทธ๋ƒฅ passํ•ด์ฃผ๊ณ , ์กด์žฌํ•œ๋‹ค๋ฉด ์ ์ˆ˜๋ฅผ ์ฑ„์›Œ์ฃผ์—ˆ๋‹ค. 

์ •ํ•ด์ค˜์•ผ ํ•˜๋Š” ์ž์‹๋งŒํผ ๊ณ„์‚ฐ์„ ํ•ด์ฃผ์—ˆ๋‹ค๋ฉด while๋ฌธ์„ ๋น ์ ธ๋‚˜์˜ค๊ฒŒ ํ–ˆ๋‹ค. 

 

๋งˆ์ง€๋ง‰ m๋งŒํผ ์ž…๋ ฅ๋ฐ›์€ ๊ท€์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๋ฅผ map์—์„œ ์ฐพ์•„ ๋น„๊ตํ•ด๊ฐ€๋ฉด์„œ ์ตœ๋Œ“๊ฐ’์„ ๊ฐ–๋Š” ๊ท€์กฑ์˜ ์ด๋ฆ„์„ ์ถœ๋ ฅํ•ด์ฃผ๋ฉด ๋!

 

โŒ์ฒซ๋ฒˆ์งธ ์ œ์ถœ

์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋‚ฌ๋‹ค. ์†”์งํžˆ ์ฒ˜์Œ๋ถ€ํ„ฐ ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์“ฐ๋ฉด ๋  ๊ฒƒ ๊ฐ™๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋Š”๋ฐ n๊ณผ m์˜ ์ตœ๋Œ€๊ฐ€ 50์ด๊ธธ๋ž˜ ๊ตณ์ด ์“ฐ์ง€ ์•Š์•„๋„ ๋  ์ค„ ์•Œ์•˜๋Š”๋ฐ...


๐Ÿ’ก๋‘๋ฒˆ์งธ ์•„์ด๋””์–ด

๋งŒ์•ฝ ๋ถ€๋ชจ๊ฐ€ ํ•˜๋‚˜ ๋˜๋Š” ๋‘˜์ด ์™•์กฑ์ผ ๋•Œ ๊ทธ ๋ถ€๋ชจ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ์—” sovleํ•จ์ˆ˜๋ฅผ ์žฌ๊ท€ํ˜ธ์ถœํ•˜์—ฌ ๊ทธ ๋ถ€๋ชจ๋ฅผ ์ž์‹ ์ทจ๊ธ‰ํ•˜์—ฌ ์™•์กฑ ์ ์ˆ˜๋ฅผ ์ฐพ์•„์ฃผ๋Š” ๋ฐฉ์‹์œผ๋กœ ํ’€์—ˆ๋‹ค. 

 

๐Ÿ”ฅํ’€์ด๐Ÿ”ฅ

์ž์‹์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ 0์ผ ๋•Œ ์•„๋ž˜์˜ ๊ฒฝ์šฐ์— ๋”ฐ๋ผ ์™•์กฑ ์ ์ˆ˜๋ฅผ ๋‹ค๋ฅด๊ฒŒ ๊ตฌํ•œ๋‹ค.

1. ๋ถ€๋ชจ ํ•œ์ชฝ๋งŒ ์™•์กฑ

  1-1. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ(0์ด ์•„๋‹Œ ๊ฒฝ์šฐ)

  1-2. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ (0์ธ ๊ฒฝ์šฐ)

2. ๋ถ€๋ชจ ์–‘์ชฝ ๋‹ค ์™•์กฑ

  2-1. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ๋‘˜๋‹ค ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ

  2-2. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์™ผ์ชฝ ๋ถ€๋ชจ๋งŒ ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ

  2-3. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์˜ค๋ฅธ์ชฝ ๋ถ€๋ชจ๋งŒ ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ

  2-4. ๊ทธ ์™•์กฑ์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ๋‘˜๋‹ค ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ

 

 

1-1๊ณผ 2-1์˜ ๊ฒฝ์šฐ์—”

๋ถ€๋ชจ์˜ ์™•์กฑ ์ ์ˆ˜๋ฅผ ๊ฐ๊ฐ /2ํ•ด์„œ ๋”ํ•ด์ค€๋‹ค.

1-2, 2-2, 2-3, 2-4์˜ ๊ฒฝ์šฐ์—”

๋ถ€๋ชจ์˜ ์™•์กฑ ์ ์ˆ˜๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด ๋ถ€๋ชจ๋ฅผ ์ž์‹์ทจ๊ธ‰ํ•˜์—ฌ ์™•์กฑ์ ์ˆ˜๋ฅผ ์ฐพ๋Š” ํ•จ์ˆ˜๋ฅผ ์žฌ๊ท€ํ˜ธ์ถœํ•ด์ฃผ๊ณ , 

์žฌ๊ท€ํ˜ธ์ถœ๋กœ ์ธํ•ด ์ •ํ•ด์ง„ ๋ถ€๋ชจ์˜ ์™•์กฑ ์ ์ˆ˜๋กœ ์ž์‹์˜ ์™•์กฑ ์ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•ด์ค€๋‹ค.

์ž์‹์˜ ์™•์กฑ ์ ์ˆ˜๊ฐ€ ์ •ํ•ด์ง€๋ฉด return

 

๋งˆ์ง€๋ง‰์œผ๋กœ ์™•์œ„ ๊ณ„์Šน์„ ์ฃผ์žฅํ•˜๋Š” ๊ท€์กฑ๋“ค์˜ ์™•์กฑ ์ ์ˆ˜๋ฅผ ๋น„๊ตํ•ด ๊ฐ€์žฅ ํฐ ์™•์กฑ ์ ์ˆ˜๋ฅผ ๊ฐ€์ง„ ๊ท€์กฑ์˜ ์ด๋ฆ„์„ ์ถœ๋ ฅํ•œ๋‹ค.


#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

int n, m;
string first_king;
string input[51][3];

map<string, pair<pair<string, string>, double>> family;

void solve(string child, string par_left, string par_right) {
    if (family[child].second == 0) {
        if (family.count(par_left) && family.count(par_right)) {
            double left_num = family[par_left].second;
            double right_num = family[par_right].second;
            if (left_num != 0 && right_num != 0) {
                family[child] = {{par_left, par_right}, left_num / 2 + right_num / 2};
            } else if (left_num != 0 && right_num == 0) {
                solve(par_left, family[par_left].first.first, family[par_left].first.second);
                right_num = family[par_left].second;
                family[child] = {{par_left, par_right}, left_num / 2 + right_num / 2};
            } else if (left_num == 0 && right_num != 0) {
                solve(par_right, family[par_right].first.first, family[par_right].first.second);
                left_num = family[par_right].second;
                family[child] = {{par_left, par_right}, left_num / 2 + right_num / 2};
            } else {
                solve(par_left, family[par_left].first.first, family[par_left].first.second);
                right_num = family[par_left].second;
                solve(par_right, family[par_right].first.first, family[par_right].first.second);
                left_num = family[par_right].second;
                family[child] = {{par_left, par_right}, left_num / 2 + right_num / 2};
            }
        } else if (family.count(par_left) && !family.count(par_right)) {
            double left_num = family[par_left].second;
            if (left_num != 0) {
                family[child] = {{par_left, par_right}, left_num / 2};
            } else {
                solve(par_left, family[par_left].first.first, family[par_left].first.second);
                left_num = family[par_left].second;
                family[child] = {{par_left, par_right}, left_num / 2};
            }
        } else if (!family.count(par_left) && family.count(par_right)) {
            double right_num = family[par_right].second;
            if (right_num != 0) {
                family[child] = {{par_left, par_right}, right_num / 2};
            } else {
                solve(par_right, family[par_right].first.first, family[par_right].first.second);
                right_num = family[par_left].second;
                family[child] = {{par_left, par_right}, right_num / 2};
            }
        }
        return;
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    cin >> first_king;

    family.insert({first_king, {{"", ""}, 1}});
    string a, b, c;
    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        family.insert({a, {{b, c}, 0}});
        input[i][0] = a;
        input[i][1] = b;
        input[i][2] = c;
    }
    for (int i = 0; i < n; i++) {
        string child = input[i][0];
        string par_left = input[i][1];
        string par_right = input[i][2];

        if (family[child].second == 0) {
            solve(child, par_left, par_right);
        }
    }


    string s;
    double large = 0;
    string large_man = "";
    for (int i = 0; i < m; i++) {
        cin >> s;
        if (large < family[s].second) {
            large_man = s;
            large = family[s].second;
        }
    }
    cout << large_man;


}
728x90
๋ฐ˜์‘ํ˜•

'PS > C++' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€/C++] 11054๋ฒˆ ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด  (0) 2022.07.20
[๋ฐฑ์ค€/C++] 11053๋ฒˆ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด  (0) 2022.07.20
[๋ฐฑ์ค€/C++] 11057๋ฒˆ ์˜ค๋ฅด๋ง‰ ์ˆ˜  (0) 2022.07.18
[๋ฐฑ์ค€/C++] 1939๋ฒˆ ์ค‘๋Ÿ‰์ œํ•œ  (0) 2022.07.18
[๋ฐฑ์ค€/C++] 14716๋ฒˆ ํ˜„์ˆ˜๋ง‰  (0) 2022.07.16
'PS/C++' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€/C++] 11054๋ฒˆ ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด
  • [๋ฐฑ์ค€/C++] 11053๋ฒˆ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด
  • [๋ฐฑ์ค€/C++] 11057๋ฒˆ ์˜ค๋ฅด๋ง‰ ์ˆ˜
  • [๋ฐฑ์ค€/C++] 1939๋ฒˆ ์ค‘๋Ÿ‰์ œํ•œ
yulee_to
yulee_to
  • yulee_to
    yulee
    yulee_to
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ์ „์ฒด ๊ธ€ (113) N
      • CS (2)
        • OS (0)
        • DB (0)
        • Network (2)
      • Develop (21)
        • Spring (9)
        • Java (12)
        • Python (0)
        • Algorithm (0)
        • ๊ธฐํƒ€ (0)
      • PS (39)
        • C++ (39)
        • Java (0)
      • Book (39)
        • ์ž๋ฐ”์˜ ์‹  (32)
        • ์Šคํ”„๋ง ์ž…๋ฌธ์„ ์œ„ํ•œ ์ž๋ฐ” ๊ฐ์ฒด ์ง€ํ–ฅ์˜ ์›๋ฆฌ์™€ ์ดํ•ด (7)
      • ETC (4)
        • Blog (3)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ํ™ˆ
    • ํƒœ๊ทธ
    • ๋ฐฉ๋ช…๋ก
  • ๋งํฌ

  • ๊ณต์ง€์‚ฌํ•ญ

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    ์ž๋ฐ”์˜ ์‹ 
    ์Šคํ”„๋ง ์ž…๋ฌธ
    DP
    ๊ฐ์ฒด์ง€ํ–ฅ
    ์ž๋ฐ”
    boj
    C++
    EC2
    GodOfJava
    ์—์Šค๋„ท์‹œ์Šคํ…œ
    1์ผ1๋ฐฑ์ค€
    TiL
    ์•Œ๊ณ ๋ฆฌ์ฆ˜
    ์œ„์ƒ์ •๋ ฌ
    ์Šคํ„ฐ๋””
    ๋ฉ€ํ‹ฐ์บ ํผ์Šค
    ๋ฌธ์ œํ’€์ด
    Spring
    Java
    ๋ฐฑ์ค€
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
yulee_to
[๋ฐฑ์ค€/C++] 5021๋ฒˆ ์™•์œ„๊ณ„์Šน
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”