Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 초사각형(Hyperrectangle) 셀 값의 합계 구하는 방법

문제 개요

하이퍼렉탱글(초사각형)은 k개의 차원을 가진 직사각형의 일반화된 개념입니다. 각 차원의 길이는 n1, n2, n3, ..., nm으로 표현되며, 초사각형의 각 셀은 (p, q, r, ...) 형태의 좌표로 주소가 지정됩니다. 이때 각 셀의 값은 해당 좌표들의 최대공약수, 즉 gcd(p, q, r, ...)와 같습니다. 좌표 범위는 1 ≤ p ≤ n1, 1 ≤ q ≤ n2 등으로 제한되며, 인덱스는 1부터 시작합니다.

우리의 과제는 모든 셀 값 gcd(p, q, r, ...)의 총합을 계산한 뒤, 그 결과를 10^9 + 7로 나눈 나머지로 반환하는 것입니다.

예시로 이해하기

입력이 input_arr = [[2, 2], [5, 5]]와 같다면 출력은 [5, 37]이 됩니다. 두 개의 테스트 인스턴스가 주어지며, 각 인스턴스마다 셀 값의 합계를 따로 계산해야 합니다.

첫 번째 인스턴스: 2×2 초사각형

(p, q)   gcd(p, q)
(1, 1)   1
(1, 2)   1
(2, 1)   1
(2, 2)   2

GCD의 합계 = 1 + 1 + 1 + 2 = 5

두 번째 인스턴스: 5×5 초사각형

행 1: 1 1 1 1 1 → 행 합계 5
행 2: 1 2 1 2 1 → 행 합계 7
행 3: 1 1 3 1 1 → 행 합계 7
행 4: 1 2 1 4 1 → 행 합계 9
행 5: 1 1 1 1 5 → 행 합계 9

GCD의 합계 = 5 + 7 + 7 + 9 + 9 = 37

해결 접근 방법

모든 셀을 일일이 순회하면서 GCD를 직접 계산하는 것은 차원과 크기가 커질수록 매우 비효율적입니다. 대신 포함-배제 원리(뫼비우스 반전 아이디어)를 활용하면 효율적으로 답을 구할 수 있습니다.

핵심 아이디어는 다음과 같습니다. "모든 좌표가 i의 배수인 셀의 개수"를 f(i)라고 하면, f(i)는 각 차원 길이를 i로 나눈 몫을 모두 곱한 값이 됩니다. f(i)에는 GCD가 i의 배수인 모든 셀이 포함되므로, 큰 값부터 역순으로 계산하면서 이미 구한 배수들의 기여를 빼주면 GCD가 정확히 i인 셀의 개수 g(i)를 얻을 수 있습니다. 최종 답은 Σ i × g(i)입니다.

이를 구현하기 위해 다음 단계를 따릅니다.

  1. coeff_find() 함수 정의 — test_instance와 i를 매개변수로 받습니다.
    • value := 1로 초기화합니다.
    • test_instance의 각 차원 길이 k에 대해 value := value × (k // i)를 수행합니다. 즉, 각 차원에서 i의 배수 좌표 개수를 곱합니다.
    • value를 반환합니다.
  2. 메인 함수(solve)의 처리 흐름
    • output := 새 리스트를 생성합니다.
    • input_arr의 각 test_instance에 대해 다음을 수행합니다.
      • min_value := test_instance의 최솟값
      • total_value := 0으로 초기화
      • temp_dict := 새 딕셔너리(맵) 생성
      • i를 min_value부터 1까지 1씩 감소시키며 반복합니다.
        • p := coeff_find(test_instance, i)
        • q := i로 설정한 뒤, q가 min_value 이하인 동안 q := q + i를 반복하며, q가 temp_dict에 이미 존재하면 p := p − temp_dict[q]로 뺍니다.
        • temp_dict[i] := p를 저장합니다.
        • total_value := total_value + temp_dict[i] × i를 누적합니다.
      • 내부 반복이 끝나면 output 리스트의 끝에 total_value mod (10^9 + 7)을 추가합니다.
    • 모든 인스턴스를 처리한 후 output을 반환합니다.

구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

def coeff_find(test_instance, i):
    value = 1
    for k in test_instance:
        value *= k // i
    return value

def solve(input_arr):
    output = []
    for test_instance in input_arr:
        min_value = min(test_instance)
        total_value = 0
        temp_dict = {}
        for i in range(min_value, 0, -1):
            p = coeff_find(test_instance, i)
            q = i
            while q <= min_value:
                q += i
                if q in temp_dict:
                    p -= temp_dict[q]
            temp_dict[i] = p
            total_value += temp_dict[i] * i
        output.append(total_value % (10**9 + 7))
    return output

print(solve([[2, 2], [5, 5]]))

입력

[[2, 2], [5, 5]]

출력

[5, 37]

마무리

이 알고리즘은 전체 셀을 하나씩 순회하는 O(n1 × n2 × ... × nm) 방식보다 훨씬 효율적입니다. 각 인스턴스에 대해 대략 O(min_value × log(min_value)) 시간 안에 답을 계산할 수 있어, 차원의 수와 크기가 큰 문제에서도 실용적으로 동작합니다. 포함-배제 원리를 활용한 이러한 접근법은 GCD 합계뿐 아니라 약수 개수 세기, 배수 관련 카운팅 문제 등 다양한 조합론적 문제에도 응용할 수 있습니다.