n개의 행과 m개의 열로 이루어진 행렬이 주어졌다고 가정해 보겠습니다. 우리가 구해야 할 것은 행렬 안에서 GCD(최대공약수)가 1보다 큰 연속된 요소들의 최대 개수입니다. 여기서 '연속된 요소'란 행렬에서 가로 방향 또는 세로 방향으로 이어져 있는 요소들을 의미합니다.
문제 예시
예를 들어 다음과 같은 입력이 주어졌다고 합시다.
| 3 | 7 | 9 | 12 |
| 5 | 9 | 4 | 6 |
| 7 | 8 | 5 | 10 |
m = 4, n = 3일 때 출력 결과는 3입니다.
그 이유는 주어진 행렬의 네 번째 열이 12, 6, 10으로 구성되어 있고, 이 열 요소들의 GCD가 2이기 때문입니다. 해당 구간에는 세 개의 요소가 있으므로 정답은 3이 됩니다.
해결 접근 방법
이 문제는 누적 GCD와 3차원 배열을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 특정 행 구간(i행부터 j행까지)에 대해 각 열별 GCD를 미리 계산해 두고, 이를 가로 방향으로 확장하며 연속 구간의 길이를 추적하는 것입니다. 단계별 과정은 다음과 같습니다.
- m × n × n 크기의 새로운 3차원 리스트
mat을 생성하고, 결과값res를 0으로 초기화합니다. - 시작 행
i와 끝 행j(i ≤ j)를 결정하는 이중 반복문을 수행합니다. - 각 (i, j) 조합마다
gcd_temp와x를 0으로 초기화한 뒤, 열 인덱스k를 순회합니다. - i == j이면
mat[i][j][k]에 해당 행의 값을 그대로 저장하고, 그렇지 않으면 이전 누적 값mat[i][j-1][k]와 현재 행의 값input_list[j][k]의 GCD를 저장합니다. 이렇게 하면mat[i][j][k]는 i행부터 j행까지 같은 열에 있는 값들의 GCD가 됩니다. gcd_temp를 갱신하여 지금까지 확인한 열들의 전체 GCD를 추적하고, 그 값이 1보다 크면x에 (j − i + 1)을 더해 연속 구간의 길이를 누적합니다.- GCD가 1 이하로 떨어지면 지금까지의
x값으로res를 갱신하고, 현재 칸의 값이 1보다 크다면gcd_temp와x를 재설정하여 새로운 구간 탐색을 시작합니다. - 모든 반복이 끝나면
res를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n² × m × log V)(V는 원소의 최댓값) 수준으로, 행렬의 크기가 크지 않다면 충분히 빠르게 동작합니다.
예제 코드
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
from math import gcd
def solve(n, m, input_list):
mat = [[[0] * m for _ in range(n)] for _ in range(n)]
res = 0
for i in range(n):
for j in range(i, n):
gcd_temp = 0
x = 0
for k in range(m):
if i == j:
mat[i][j][k] = input_list[i][k]
else:
mat[i][j][k] = gcd(mat[i][j-1][k], input_list[j][k])
gcd_temp = gcd(gcd_temp, mat[i][j][k])
if gcd_temp > 1:
x += j - i + 1
else:
res = max(res, x)
if mat[i][j][k] > 1:
gcd_temp = mat[i][j][k]
x = j - i + 1
res = max(res, x)
return res
print(solve(3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]))입력
3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]
출력
3
실행 결과 네 번째 열(12, 6, 10)의 세 요소가 GCD 2를 공유하므로, 기대했던 대로 3이 출력되는 것을 확인할 수 있습니다.