연습 문제

이 장의 문제는 지금까지 배운 도구를 하나씩 쓰도록 만든 연습용 문제입니다. 먼저 접근 방법을 스스로 떠올려 본 다음 풀이를 확인하세요.

문제 1. 바닥 타일

가로 W, 세로 H(센티미터, 정수)인 직사각형 바닥을 같은 크기의 정사각형 타일로 빈틈없이, 자르지 않고 덮으려고 합니다. 가능한 가장 큰 타일의 한 변 길이와 그때 필요한 타일 수를 구하세요. 예: W = 120, H = 84이면 한 변 12, 타일 70장입니다.

접근: 타일의 한 변은 W와 H를 모두 나누어야 하므로 공약수이고, 가장 큰 것은 최대공약수입니다. 타일 수는 (W / g) × (H / g)입니다.

import math

def largest_tile(w: int, h: int) -> tuple[int, int]:
    g = math.gcd(w, h)
    return g, (w // g) * (h // g)

print(largest_tile(120, 84))  # (12, 70)
print(largest_tile(7, 5))     # (1, 35)

문제 2. 동시에 깜빡이는 신호등

신호등 k개가 있고, i번째 신호등은 p_i초마다 한 번 깜빡입니다. 모든 신호등이 0초에 동시에 깜빡였습니다. 1초부터 T초까지(양 끝 포함) 모든 신호등이 동시에 깜빡이는 순간은 몇 번일까요? p_i는 최대 10^9, k는 최대 10^5, T는 최대 10^18입니다.

접근: 모두 동시에 깜빡이는 시각은 모든 주기의 공배수이므로 답은 T // lcm(p_1, …, p_k)입니다. LCM은 lcm(a, b) = a // gcd(a, b) * b로 차례로 합칩니다. LCM이 T를 넘는 순간 답은 0으로 확정되므로 계산을 멈춥니다. 이 조기 종료 덕분에 C++이나 Java로 옮겨도 오버플로를 피하기 쉽습니다.

import math

def simultaneous_blinks(periods: list[int], t: int) -> int:
    l = 1
    for p in periods:
        l = l // math.gcd(l, p) * p
        if l > t:
            return 0
    return t // l

print(simultaneous_blinks([4, 6, 10], 300))   # 5 (60, 120, 180, 240, 300)
print(simultaneous_blinks([7, 11, 13], 1000)) # 0 (lcm = 1001)

문제 3. 구간 소수 개수 질의

Q개의 질의가 주어지고, 각 질의는 L R(1 ≤ L ≤ R ≤ 10^6)입니다. 각 질의마다 L 이상 R 이하인 소수의 개수를 출력하세요. Q는 최대 10^5입니다.

접근: 질의마다 소수 판정을 하면 너무 느립니다. 체로 10^6까지 한 번에 소수를 표시하고, 누적 합 prefix[x] = x 이하의 소수 개수를 만든 뒤 답을 prefix[R] - prefix[L - 1]로 O(1)에 구합니다.

def build_prime_prefix(limit: int) -> list[int]:
    is_prime = bytearray([1]) * (limit + 1)
    is_prime[0] = is_prime[1] = 0
    i = 2
    while i * i <= limit:
        if is_prime[i]:
            is_prime[i * i :: i] = bytes((limit - i * i) // i + 1)
        i += 1
    prefix = [0] * (limit + 1)
    running = 0
    for x in range(limit + 1):
        running += is_prime[x]
        prefix[x] = running
    return prefix

prefix = build_prime_prefix(10**6)
for left, right in [(1, 10), (10, 30), (1, 10**6)]:
    print(prefix[right] - prefix[left - 1])  # 4, 6, 78498

문제 4. 격자 경로 세기

R × C 격자의 왼쪽 위에서 오른쪽 아래 꼭짓점까지, 오른쪽이나 아래로만 한 칸씩 움직이는 경로의 수를 10^9 + 7로 나눈 나머지로 구하세요. 질의가 최대 10^5개이고 R + C ≤ 2 × 10^5입니다.

접근: 총 R + C번 움직이고 그중 R번이 아래쪽이므로 답은 C(R + C, R)입니다. 팩토리얼과 역팩토리얼을 최대값까지 미리 계산해 두면 각 질의는 곱셈 두 번입니다.

MOD = 10**9 + 7
LIMIT = 2 * 10**5

fact = [1] * (LIMIT + 1)
for i in range(1, LIMIT + 1):
    fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * (LIMIT + 1)
inv_fact[LIMIT] = pow(fact[LIMIT], MOD - 2, MOD)
for i in range(LIMIT, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD

def ncr(n: int, r: int) -> int:
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD

print(ncr(2 + 2, 2))           # 6
print(ncr(3 + 7, 3))           # 120
print(ncr(100000 + 100000, 100000))  # 879467333

문제 5. 일차 합동식 풀기

정수 a, b, m(m ≥ 1)이 주어질 때 a × x ≡ b (mod m)을 만족하는 0 ≤ x < m인 해를 모두 구하세요. 해가 없으면 빈 목록을 돌려줍니다.

접근: g = gcd(a, m)이라고 하면 a × x - m × y = b가 정수해를 가질 조건은 g가 b를 나누는 것입니다. 나누어떨어지면 양변을 g로 나눈 (a/g) × x ≡ (b/g) (mod m/g)에서 a/g와 m/g가 서로소이므로 역원으로 해 x0를 하나 구하고, x0 + k × (m/g)(k = 0 … g-1)가 전체 해입니다.

def gcd_with_coeff(a: int, b: int) -> tuple[int, int]:
    """(g, x)를 돌려준다. a * x ≡ g (mod b), g = gcd(a, b)"""
    old_r, r, old_x, x = a, b, 1, 0
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
    return old_r, old_x

def solve_linear_congruence(a: int, b: int, m: int) -> list[int]:
    a, b = a % m, b % m
    g, x = gcd_with_coeff(a, m)
    if b % g != 0:
        return []
    step = m // g
    x0 = (x * (b // g)) % step
    return [x0 + k * step for k in range(g)]

print(solve_linear_congruence(14, 30, 100))  # [45, 95]
print(solve_linear_congruence(4, 3, 6))      # [] — gcd 2가 3을 나누지 않음
print(solve_linear_congruence(3, 1, 7))      # [5] — 3의 역원

여기서는 y 계수가 필요 없어서 확장 유클리드에서 x만 추적합니다. x는 a × x ≡ g (mod m)을 만족하므로 b / g를 곱하면 a × x ≡ b가 됩니다. 마지막에 step으로 나머지를 취해 가장 작은 해를 얻습니다.

정리

GCD는 "같은 크기로 나누기", LCM은 "주기가 다시 겹치는 때", 체와 누적 합은 "범위 안의 소수를 여러 번", 팩토리얼 전처리는 "이항 계수를 여러 번", 확장 유클리드는 "역원이나 합동식"이 보이면 떠올리세요. 문제를 보면 먼저 어떤 도구가 필요한지 고르고, 그다음 입력 범위로 오버플로와 시간 제한을 점검하는 순서가 좋습니다.