알고리즘 문제/BOJ

4690번 완전 세제곱

parkit 2018. 12. 9. 20:00
728x90
반응형

https://www.acmicpc.net/problem/4690


2가지 풀이 방법이 있다.


1. 백트래킹

2. 단순 for문


이 문제의 경우 2번이 더 간결하고, 빠르다.


백트래킹

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef struct abcd
{
    int a;
    int b;
    int c;
    int d;
}abcd;
 
vector<int> b, c, d;
 
vector<abcd> ABCD;
 
int result = -1;
 
bool cmp(const abcd &A, const abcd &B)
{
    if (A.a < B.a) return true;
    else if (A.a == B.a) if (A.b < B.b) return true;
 
    return false;
}
 
void Chk(vector<int> v)
{
    if (v.size() == 3)
    {
        for (int i = 0; i < 2; i++)
        {
            if (v.at(i) > v.at(i + 1)) return;
        }
 
        int sum = 0;
 
        for (auto i : v) sum += (int)pow(i, 3);
 
        for (int i = 6; i <= 100; i++)
        {
            if ((int)pow(i, 3) == sum)
            {
                int a = 0;
 
                ABCD.push_back({ i, v.at(0), v.at(1), v.at(2) });
            }
        }
 
        return;
    }
 
    for (int i = 0; i < b.size(); i++)
    {
        v.push_back(b.at(i));
 
        for (int j = 0; j < c.size(); j++)
        {
            if (b.at(i) >= c.at(j))
            {
                continue;
            }
 
            v.push_back(c.at(j));
 
            for (int k = 0; k < d.size(); k++)
            {
                if (c.at(j) >= d.at(k)) continue;
 
                v.push_back(d.at(k));
 
                Chk(v);
 
                v.pop_back();
            }
 
            v.pop_back();
        }
 
        v.pop_back();
    }
}
 
int main(void)
{
    for (int i = 2; i <= 90; i++)
    {
        b.push_back(i);
        c.push_back(i);
        d.push_back(i);
    }
 
    vector<int> vc;
 
    Chk(vc);
 
    sort(ABCD.begin(), ABCD.end(), cmp);
 
    for (auto i : ABCD)
    {
        printf("Cube = %d, Triple = (%d,%d,%d)\n", i.a, i.b, i.c, i.d);
    }
 
    return 0;
}
cs







단순 for문

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
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void)
{
    int a = 0, b = 0, c = 0, d = 0;
 
    for(a = 6; a <= 100; a++)
        for(b = 2; b < a; b++)
            for(c = b + 1; b*b*b + c*c*c < a*a*a; c++)
                for(d = c + 1; b*b*b + c*c*c + d*d*d <= a*a*a; d++)
                    if(a*a*a == b*b*b + c*c*c + d*d*d)
                        printf("Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d);
 
    return 0;
}
cs








728x90
반응형
저작자표시 (새창열림)