모든 챌린지
보통 1명 해결 정답률 100.0%

직각삼각형 세 수 찾기

지정된 둘레를 가지는 모든 정수 직각삼각형을 나열하세요.

배우게 될 내용

  • 주어진 둘레의 정수 직각삼각형 모두 나열하기
  • 변의 순서를 정해 중복 피하기
  • 범위 제한으로 탐색 가지치기

문제

원문 보기 (영어)

양의 정수 a < b < c에 대해 a² + b² = c²이고 a + b + c = perimeter인 모든 세 수의 조합을 찾으세요. 각 조합은 [a, b, c] 형태로, a가 증가하는 순서, 그 다음 b가 증가하는 순서로 정렬하여 반환하세요. 같은 변의 순서만 바꾼 경우는 포함하지 마세요.

pythagorean_triplets(perimeter)를 구현하세요.

입력

perimeter: 세 변의 합으로 요구되는 값입니다.

출력

지정된 순서대로 세 수의 조합 리스트를 반환하세요.

제약 조건

3 ≤ perimeter ≤ 100,000. 조건을 만족하는 삼각형이 없다면 빈 리스트를 반환하세요.

예시

예시 1
입력:
perimeter = 30

예상 출력:
expected = [
    [5, 12, 13]
]
입력:
long long perimeter = 30;

예상 출력:
std::vector<std::vector<long long>> expected = {
    {5, 12, 13}
};
입력:
long perimeter = 30;

예상 출력:
long[][] expected = new long[][] {
    new long[] {5, 12, 13}
};

설명

5 + 12 + 13 = 30이고 5² + 12² = 13²입니다. 이 경우가 유일한 조합입니다.

예시 2
입력:
perimeter = 11

예상 출력:
expected = []
입력:
long long perimeter = 11;

예상 출력:
std::vector<std::vector<long long>> expected = {};
입력:
long perimeter = 11;

예상 출력:
long[][] expected = new long[][] {};

설명

증가하는 양의 정수 직각삼각형 세 수의 합이 11이 되는 경우는 없습니다.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

유효한 삼중항은 피타고라스 식과 둘레 합을 모두 만족해야 합니다.

힌트 2

모든 변의 순서를 다 시도하지 말고, 둘레를 이용해 탐색 범위를 제한하세요.

힌트 3

반드시 a c b c c만 유지하고, 대칭적인 변 선택으로 생기는 중복은 건너뛰세요.

예상 복잡도

시간 O(n^2), 추가 공간 O(1)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 ННикита Python 857 ms - 4/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 1개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.