프로그래머스

프로그래머스 멀쩡한 사각형 풀이: 최대공약수로 대각선 격자 계산

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 멀쩡한 사각형
  • 출처: 프로그래머스, Summer/Winter Coding(2019)
  • 자체 판단 난이도: Level 2

가로와 세로가 최대 1억이므로 모든 1cm 정사각형을 직접 확인할 수 없다. 대각선이 지나는 정사각형 개수를 최대공약수로 계산하는 수식만 도출하면 반복문 없이 해결할 수 있어 Level 2로 판단한다.

1. 문제 요약

가로 W, 세로 H인 직사각형 종이가 있고, 모든 격자는 1cm × 1cm 정사각형으로 나뉘어 있다. 종이의 한 대각선으로 잘라진 뒤에도 온전하게 사용할 수 있는 정사각형의 개수를 구해야 한다.

대각선이 지나간 정사각형은 잘려서 사용할 수 없으므로, 전체 정사각형 수에서 대각선이 지나는 정사각형 수를 빼면 된다.

전체 정사각형 수 = W * H

W, H는 각각 1억 이하의 자연수이므로 W * H는 큰 정수가 될 수 있다. Python은 정수 범위를 자동으로 확장하지만, 다른 언어에서는 64비트 정수형을 사용해야 한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

수식 도출

g = gcd(W, H)라고 하고 가로·세로를 다음처럼 나눈다.

W = g * w'
H = g * h'

w'와 h'는 서로소다. 원래 직사각형은 w' × h' 크기의 동일한 패턴이 g번 반복되는 구조로 볼 수 있다.

서로소인 w' × h' 패턴에서 대각선은 내부 세로 격자선 w' - 1개와 내부 가로 격자선 h' - 1개를 지나간다. 서로소이므로 대각선이 격자 교점에 정확히 걸쳐 두 선을 동시에 지나는 경우가 없고, 대각선이 지나가는 정사각형 수는 다음과 같다.

(w' - 1) + (h' - 1) + 1 = w' + h' - 1

이 패턴이 g번 반복되므로 손상되는 정사각형 수는 다음과 같다.

g * (w' + h' - 1)
= g * (W / g + H / g - 1)
= W + H - g

따라서 정답은 다음 수식이다.

W * H - (W + H - gcd(W, H))

최대공약수가 대각선의 반복 단위를 정하는 이유

대각선이 지나는 칸 수는 대각선의 기울기를 매 칸마다 시뮬레이션할 필요 없이, 가로·세로 길이의 최대공약수로 나눈 최소 반복 패턴에서 계산할 수 있다. 최대공약수가 클수록 대각선이 격자 교점을 만나는 반복 주기가 짧아지고, 같은 패턴이 여러 번 반복된다.

예를 들어 W = 8, H = 12이면 gcd(8, 12) = 4다. 손상되는 칸은 8 + 12 - 4 = 16개이고, 전체 96개 중 멀쩡한 칸은 96 - 16 = 80개다.

수식의 경계 처리

W = H = 1이면 전체 칸은 하나이고 대각선이 그 칸을 지나므로 사용할 수 있는 칸은 0개다.

W와 H가 서로소이면 gcd(W, H) = 1이므로 손상되는 칸 수는 W + H - 1이다. 반대로 W와 H가 같으면 모든 작은 정사각형의 대각선이 지나므로 손상되는 칸 수는 W개이고 정답은 W * W - W다.

오답 접근과 반례

직사각형의 모든 정사각형을 순회하면서 대각선이 지나가는지 확인하면 W * H에 비례하는 시간과 공간이 필요하다. W = H = 100,000,000에서는 정사각형이 10^16개이므로 이 방법은 실행할 수 없다.

손상되는 칸 수를 단순히 W + H로 계산하면 시작 칸 또는 끝 칸의 중복을 보정하지 못한다.

W = 8, H = 12
잘못된 손상 칸 수: 20
실제 손상 칸 수: 8 + 12 - gcd(8, 12) = 16

두 방향의 격자선이 같은 내부 교점에서 만나는 횟수를 최대공약수로 보정해야 한다.

시간·공간 복잡도

유클리드 호제법으로 최대공약수를 구하므로 시간 복잡도는 O(log(min(W, H)))이다. 추가 배열 없이 정수 변수만 사용하므로 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

from math import gcd


def solution(w, h):
    broken = w + h - gcd(w, h)
    return w * h - broken

gcd(w, h)는 유클리드 호제법을 사용하는 Python 표준 라이브러리 함수다. broken은 대각선이 지나가 사용할 수 없는 정사각형 수이고, 전체 개수에서 이를 뺀 값을 반환한다.

gcd를 직접 구현하는 방법

표준 라이브러리를 사용할 수 없거나 유클리드 호제법의 동작을 직접 확인하고 싶다면, 나머지가 0이 될 때까지 (a, b)를 (b, a % b)로 바꾸면 된다.

def greatest_common_divisor(a, b):
    while b:
        a, b = b, a % b
    return a


def solution(w, h):
    gcd = greatest_common_divisor(w, h)
    return w * h - (w + h - gcd)

예를 들어 gcd(8, 12)는 다음 순서로 계산된다.

(8, 12) -> (12, 8) -> (8, 4) -> (4, 0)

두 번째 값이 0이 된 시점의 첫 번째 값 4가 최대공약수다. 직접 구현한 경우에도 유클리드 호제법의 시간 복잡도는 O(log(min(W, H))), 추가 공간 복잡도는 O(1)이다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 정사각형과 공약수가 있는 직사각형의 손상 칸 수를 확인할 수 있다.

assert solution(8, 12) == 80
assert solution(3, 3) == 6

4. 공식 예제와 추가 검증

공식 예제와 한 변이 1인 경우, 정사각형, 서로소인 변, 최대 입력에 가까운 값을 Python 코드로 실행했다.

공식 예제

입력: W = 8, H = 12
기대 출력: 80
확인 결과: 통과
검증 목적: gcd(8, 12) = 4를 이용해 손상 칸 16개를 계산하는지 확인

추가 검증 1: 한 변이 1인 경우

입력: W = 1, H = 1
기대 출력: 0
확인 결과: 통과
검증 목적: 대각선이 유일한 정사각형을 지나가는 최소 입력 확인

추가 검증 2: 정사각형 종이

입력: W = 3, H = 3
기대 출력: 6
확인 결과: 통과
검증 목적: gcd(W, H) = W인 경우 모든 대각선 패턴을 처리하는지 확인

추가 검증 3: 서로소인 가로·세로

입력: W = 5, H = 7
기대 출력: 24
확인 결과: 통과
검증 목적: gcd(5, 7) = 1인 경우 손상 칸 W + H - 1을 적용하는지 확인

추가 검증 4: 큰 입력

입력: W = 100000000, H = 100000000
기대 출력: 9999999900000000
확인 결과: 통과
검증 목적: 전체 칸을 순회하지 않고 큰 정수 결과를 계산하는지 확인

5. 다른 풀이 방식 검색 및 비교

대각선의 기울기를 이용해 각 열의 손상 칸을 올림 계산하는 방식도 가능하다. 하지만 W, H가 매우 크고 대각선 패턴이 반복되므로, 최대공약수로 반복 패턴을 압축한 뒤 W + H - gcd(W, H)라는 수식으로 계산하는 방식이 더 간단하고 안전하다.

마무리

멀쩡한 사각형은 큰 격자를 직접 시뮬레이션하지 않고 대각선이 지나는 칸 수를 수식으로 바꾸는 문제다. 가로와 세로 길이의 최대공약수로 최소 반복 패턴을 찾으면 손상되는 정사각형 수가 W + H - gcd(W, H)가 되고, 전체 칸에서 이를 빼면 O(log(min(W, H))) 시간에 답을 구할 수 있다.

#수학#프로그래머스#난이도 2