문제
a^3 = b^3 + c^3 + d^3을 만족하는 모든 (a, b, c, d) 조합을 구하라. 단 2 <= b < c < d < a <= 100.
입력
없음.
출력
조건을 만족하는 모든 조합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
| (없음) | Cube = 6, Triple = (3,4,5) 등 |
풀이
4중 반복문으로 가능한 모든 조합을 전수탐색한다.
- a를 6부터 100까지 순회한다
- b를 2부터 a-1, c를 b+1부터 a-1, d를 c+1부터 a-1까지 순회한다
a^3 == b^3 + c^3 + d^3이면 결과를 출력한다
핵심 아이디어: a의 범위가 100 이하로 작아 4중 반복문(약 100^4 미만)으로도 충분히 빠르게 전수탐색할 수 있다.
코드
#include <iostream>
using namespace std;
int main()
{
for (int a = 6; a <= 100; a++)
for (int b = 2; b < a; b++)
for (int c = b + 1; c < a; c++)
for (int d = c + 1; d < a; d++)
if (a * a * a == b * b * b + c * c * c + d * d * d)
cout << "Cube = " << a << ", Triple = (" << b << ',' << c << ',' << d << ")\n";
}복잡도
- 시간: O(N^4) (N = 100)
- 공간: O(1)