[백준 4690] 완전 세제곱 (C#, C++) - soo:bak

문제 링크

4690번 - 완전 세제곱

설명

입력이 없으며, 네 개의 양의 정수에 대한 특정 세제곱 등식을 만족하는 모든 조합을 찾는 문제입니다.

첫 번째 수는 2 이상 100 이하이고, 나머지 세 수는 모두 첫 번째 수보다 작으며 2 이상입니다.

나머지 세 수는 비내림차순으로 정렬되어 있어야 하고, 첫 번째 수의 세제곱이 나머지 세 수의 세제곱 합과 같아야 합니다.

모든 조합을 첫 번째 수가 증가하는 순서로, 같은 첫 번째 수에서는 나머지 세 수가 사전순으로 증가하는 순서로 출력합니다.

접근법

첫 번째 수를 2부터 100까지 순회하며, 각 첫 번째 수에 대해 나머지 세 수의 모든 가능한 조합을 확인합니다.

나머지 세 수는 각각 2 이상이면서 첫 번째 수보다 작아야 하고, 비내림차순을 유지해야 하므로 중첩 반복문으로 순회합니다.

각 조합마다 네 수의 세제곱을 계산하여 첫 번째 수의 세제곱이 나머지 세 수의 세제곱 합과 같은지 확인합니다.

조건을 만족하면 지정된 형식으로 출력합니다.

첫 번째 수는 최대 100이고 나머지 세 수도 100 미만이므로, 네 중 반복문의 전체 연산 횟수는 충분히 작아 완전 탐색으로 처리할 수 있습니다.

반복문을 증가하는 순서로 순회하므로 출력 순서 조건이 자연스럽게 만족됩니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      for (var a = 2; a <= 100; a++) {
        var a3 = a * a * a;

        for (var b = 2; b < a; b++) {
          var b3 = b * b * b;

          for (var c = b; c < a; c++) {
            var c3 = c * c * c;

            for (var d = c; d < a; d++) {
              var d3 = d * d * d;

              if (a3 == b3 + c3 + d3) {
                Console.WriteLine($"Cube = {a}, Triple = ({b},{c},{d})");
              }
            }
          }
        }
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

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

  for (int a = 2; a <= 100; a++) {
    int a3 = a * a * a;

    for (int b = 2; b < a; b++) {
      int b3 = b * b * b;

      for (int c = b; c < a; c++) {
        int c3 = c * c * c;

        for (int d = c; d < a; d++) {
          int d3 = d * d * d;

          if (a3 == b3 + c3 + d3)
            cout << "Cube = " << a << ", Triple = (" << b << "," << c << "," << d << ")\n";
        }
      }
    }
  }

  return 0;
}