[๋ฐฑ์ค€/C++] 14888๋ฒˆ ์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐ

2022. 7. 13. 10:30ยทPS/C++
728x90

๋ฐฑ์ค€ ๋กœ๊ณ 
๋ฐฑ์ค€

 

14888๋ฒˆ ์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐ
14888๋ฒˆ ์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐ


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

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


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

๋ธŒ๋ฃจํŠธ ํฌ์Šค, ์ฆ‰ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ฐพ์•„๋ณด๊ณ  ๊ณ„์‚ฐํ•ด ๋น„๊ตํ•ด๋ด์•ผ ์ตœ์†Ÿ๊ฐ’๊ณผ ์ตœ๋Œ“๊ฐ’์„ ์ฐพ์„ ์ˆ˜ ์žˆ๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค. 

๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ํŠธ๋ฆฌ ๋ชจ์–‘์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋ณด๋ฉด n๋ฒˆ์งธ ์—ฐ์‚ฐ ๋‹ค์Œ์— ์˜ฌ ์ˆ˜ ์žˆ๋Š” ์—ฐ์‚ฐ๋“ค์€ n๋ฒˆ์งธ ์—ฐ์‚ฐ์ด๋ผ๋Š” ๊ณตํ†ต๋œ ๊ฐ’์„ ๊ฐ€์ง€๊ณ  ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•˜๋ฏ€๋กœ DFS๋ฅผ ์ด์šฉํ•ด ํ’€๋ฉด ๋  ๊ฒƒ ๊ฐ™์•˜๋‹ค.

๊ณ„์‚ฐ ๊ฒฐ๊ณผ๋‚˜ ๊ณ„์‚ฐ ๋„์ค‘์— ๋‚˜์˜ค๋Š” ๊ฐ’๋“ค์€ ์ •์ˆ˜ํ˜•์ธ int์˜ ๋ฒ”์œ„ ์•ˆ์— ๋“ค์–ด๊ฐ€๋ฏ€๋กœ ๋ณ€์ˆ˜๋Š” int๋กœ ์„ ์–ธํ•˜๊ณ , N์˜ ๋ฒ”์œ„๊ฐ€ 11 ์ดํ•˜์ด๋ฏ€๋กœ ์ด ์•„์ด๋””์–ด๋กœ๋Š” ์‹œ๊ฐ„ ์ดˆ๊ณผ ๊ฑฑ์ •์€ ์—†์Œ!

 

 

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

main์—์„œ +, -, x, / ๋ฅผ ๊ฐ๊ฐ ํ•œ๋ฒˆ์”ฉ dfs ํ•จ์ˆ˜๋ฅผ ์‹คํ–‰์‹œ์ผœ ์ค€๋‹ค.

dfsํ•จ์ˆ˜๋Š” ์—ฐ์‚ฐ์ž๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” idx, ๋ช‡๋ฒˆ์งธ ์ˆซ์ž๊นŒ์ง€ ๊ณ„์‚ฐํ–ˆ๋Š”์ง€๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” cnt, ๊ณ„์‚ฐ ๊ฒฐ๊ณผ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” result๋ฅผ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ๋ฐ›๋Š”๋‹ค.

๋งˆ์ง€๋ง‰ ์ˆซ์ž๊นŒ์ง€ ์—ฐ์‚ฐ์„ ๋งˆ์ณค์œผ๋ฉด(cnt==n) ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ์ตœ๋Œ€,์ตœ์†Œ๋ž‘ ๋น„๊ตํ•ด์„œ ์ตœ๋Œ“๊ฐ’, ์ตœ์†Ÿ๊ฐ’์„ ์—…๋ฐ์ดํŠธ.

์—ฐ์‚ฐํ•ด์•ผ ํ•  ์ˆซ์ž๊ฐ€ ๋‚จ์•˜์œผ๋ฉด ๋”ํ•˜๊ธฐ๋ถ€ํ„ฐ ๋‚˜๋ˆ„๊ธฐ๊นŒ์ง€ 4๋ฒˆ์˜ for๋ฌธ์„ ๋„๋Š”๋ฐ ์—ฐ์‚ฐ์ž๊ฐ€ ๋‚จ์•„์žˆ๋Š” ์—ฐ์‚ฐ์ž๋ณ„๋กœ result ๊ฐ’์„ ์—…๋ฐ์ดํŠธ ํ•ด์„œ dfs๋ฅผ ์žฌ๊ท€์ ์œผ๋กœ ์ˆ˜ํ–‰ํ•œ๋‹ค.

์ด๋•Œ ์—ฐ์‚ฐ์ž๋ฅผ ์‚ฌ์šฉํ–ˆ์Œ์„ ๋‚˜ํƒ€๋‚ด๊ธฐ ์œ„ํ•ด ์—ฐ์‚ฐ์ž ๊ฐœ์ˆ˜๋ฅผ ์ €์žฅํ•œ ๋ฐฐ์—ด์˜ ๊ฐ’์„ -1ํ•ด์ค€๋‹ค.

 


์˜ค๋žœ๋งŒ์— ํ•œ๋ฒˆ์— ์„ฑ๊ณต!

๋งž์•˜์Šต๋‹ˆ๋‹ค.

 

์•„๋ž˜๋Š” ์ œ์ถœํ•œ ์ฝ”๋“œ์ด๋‹ค.

#include <iostream>

using namespace std;

int n;
int op[4];
int num[12];
int min_num = 1000000000;
int max_num = -1000000000;

void check(int x) {
    if (min_num > x) min_num = x;
    if (max_num < x) max_num = x;
}

void dfs(int idx, int cnt, int result) {
    if (cnt == n) {
        check(result);
        return;
    }
    for (int i = 0; i < 4; i++) {
        op[idx]--;
        if (op[i] > 0) {
            if (i == 0) dfs(i, cnt + 1, result + num[cnt]);
            else if (i == 1) dfs(i, cnt + 1, result - num[cnt]);
            else if (i == 2) dfs(i, cnt + 1, result * num[cnt]);
            else if (i == 3) {
                dfs(i, cnt + 1, result / num[cnt]);
            }
        }
        op[idx]++;

    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    };
    int pl, mi, mu, di;
    cin >> pl >> mi >> mu >> di;
    for (int i = 0; i < 4; i++) {
        op[0] = pl;
        op[1] = mi;
        op[2] = mu;
        op[3] = di;
        if (op[i] > 0) {
            if (i == 0) {
                dfs(0, 2, num[0] + num[1]);
            } else if (i == 1) {
                dfs(1, 2, num[0] - num[1]);
            } else if (i == 2) {
                dfs(2, 2, num[0] * num[1]);
            } else if (i == 3) {
                dfs(3, 2, num[0] / num[1]);
            }
        }
    }
    cout << max_num << "\n" << min_num;
}
728x90

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

[๋ฐฑ์ค€/C++] 2098๋ฒˆ ์™ธํŒ์› ์ˆœํšŒ  (0) 2022.07.16
[๋ฐฑ์ค€/C++] 1753๋ฒˆ ์ตœ๋‹จ๊ฒฝ๋กœ  (0) 2022.07.15
[๋ฐฑ์ค€/C++] 1790๋ฒˆ ์ˆ˜ ์ด์–ด ์“ฐ๊ธฐ 2  (0) 2022.07.11
[๋ฐฑ์ค€/C++] 16936๋ฒˆ ๋‚˜3๊ณฑ2  (0) 2022.07.10
[๋ฐฑ์ค€/C++] 15558๋ฒˆ ์ ํ”„ ๊ฒŒ์ž„  (0) 2022.07.07
'PS/C++' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€/C++] 2098๋ฒˆ ์™ธํŒ์› ์ˆœํšŒ
  • [๋ฐฑ์ค€/C++] 1753๋ฒˆ ์ตœ๋‹จ๊ฒฝ๋กœ
  • [๋ฐฑ์ค€/C++] 1790๋ฒˆ ์ˆ˜ ์ด์–ด ์“ฐ๊ธฐ 2
  • [๋ฐฑ์ค€/C++] 16936๋ฒˆ ๋‚˜3๊ณฑ2
yulee_to
yulee_to
  • yulee_to
    yulee
    yulee_to
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ์ „์ฒด ๊ธ€ (117) 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)
      • TIL (10) N
      • Book (39)
        • ์ž๋ฐ”์˜ ์‹  (32)
        • ์Šคํ”„๋ง ์ž…๋ฌธ์„ ์œ„ํ•œ ์ž๋ฐ” ๊ฐ์ฒด ์ง€ํ–ฅ์˜ ์›๋ฆฌ์™€ ์ดํ•ด (7)
      • ETC (4)
        • Blog (3)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

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

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

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

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

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
yulee_to
[๋ฐฑ์ค€/C++] 14888๋ฒˆ ์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐ
์ƒ๋‹จ์œผ๋กœ

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