[ 백준 ] 3314 An Arithmetic Rectangle ( Python )

게시 2024/06/16

By KimJinwoo 9 분읽는 시간

BOJ 3314

산술 직사각형 채우기

안녕하세요! 오늘은 주어진 격자에서 빈 칸을 채워 산술 직사각형을 만드는 문제를 풀어보겠습니다. 산술 직사각형이란 각 행과 열에 있는 숫자들이 등차수열을 이루는 직사각형을 말합니다.

문제 접근 방법

이 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용할 수 있습니다.

주어진 격자에서 알려진 숫자들을 이용하여 선형 방정식을 세웁니다.
가우스 소거법을 사용하여 선형 방정식을 풀고, 빈 칸에 들어갈 숫자를 구합니다.
구한 숫자들로 격자를 채웁니다.

각 단계를 좀 더 자세히 살펴보겠습니다.

1. 선형 방정식 세우기

격자의 각 칸을 변수로 생각하고, 알려진 숫자들을 이용하여 선형 방정식을 세웁니다. 예를 들어, 다음과 같은 3x3 격자가 있다고 가정해보겠습니다.

1 . .
. 2 .
. . 3

이 격자에서 각 칸을 변수 $x_1$, $x_2$, $x_3$, $x_4$로 나타내면 다음과 같은 선형 방정식을 세울 수 있습니다.

\[\begin{aligned} x_1 &= 1 \\ x_2 + x_3 &= 4 \\ x_3 + x_4 &= 5 \\ x_1 + x_2 + x_3 &= 6 \\ x_2 + x_3 + x_4 &= 7 \\ x_1 + x_2 + x_3 + x_4 &= 9 \end{aligned}\]

2. 가우스 소거법을 사용하여 선형 방정식 풀기

세운 선형 방정식을 가우스 소거법을 사용하여 풉니다. 가우스 소거법은 선형 방정식을 풀기 위한 알고리즘으로, 다음과 같은 단계로 이루어집니다.

방정식을 행렬 형태로 나타냅니다.
행렬을 행 사다리꼴 형태로 변형합니다.
역대입법을 사용하여 변수의 값을 구합니다.

위의 예시에서 세운 선형 방정식을 행렬로 나타내면 다음과 같습니다.

\[\begin{bmatrix} 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 4 \\ 0 & 0 & 1 & 1 & 5 \\ 1 & 1 & 1 & 0 & 6 \\ 0 & 1 & 1 & 1 & 7 \\ 1 & 1 & 1 & 1 & 9 \end{bmatrix}\]

이 행렬을 행 사다리꼴 형태로 변형하고, 역대입법을 사용하여 변수의 값을 구하면 다음과 같은 해를 얻을 수 있습니다.

\[x_1 = 1, x_2 = 2, x_3 = 3, x_4 = 3\]

3. 격자 채우기

구한 해를 이용하여 격자의 빈 칸을 채웁니다. 위의 예시에서는 다음과 같이 격자를 채울 수 있습니다.

2 3
2 3
2 3

코드 설명

이제 주어진 코드를 단계별로 살펴보겠습니다.

  
import sys
from fractions import Fraction
from math import gcd

def reduce(f):
    if f.denominator < 0:
        f = Fraction(-f.numerator, -f.denominator)
    d = gcd(abs(f.numerator), abs(f.denominator))
    return Fraction(f.numerator // d, f.denominator // d)

sys 모듈을 사용하여 입력을 빠르게 처리합니다.
fractions 모듈에서 Fraction 클래스를 사용하여 유리수를 다룹니다.
math 모듈에서 gcd 함수를 사용하여 최대공약수를 구합니다.
reduce 함수는 주어진 분수를 기약분수로 만들어 반환합니다.

  
input = sys.stdin.readline
R, C = map(int, input().split())
A = []
for r in range(R):
    line = input().split()
    for c in range(C):
        S = line[c]
        if S == ".":
            continue
        eqn = [0] * 5
        eqn[0] = 1 - r - c + r * c
        eqn[1] = r - r * c
        eqn[2] = c - r * c
        eqn[3] = r * c
        eqn[4] = int(S)
        A.append(eqn)

input 함수를 sys.stdin.readline으로 설정하여 입력을 빠르게 처리합니다.
격자의 크기 R과 C를 입력받습니다.
격자의 각 칸에 대한 선형 방정식을 세우고, 계수 행렬 A에 저장합니다.

  
for c in range(4):
    for r in range(c, len(A)):
        if A[r][c] != 0:
            A[c], A[r] = A[r], A[c]
            break
    if c == len(A) or A[c][c] == 0:
        eqn = [0] * 5
        eqn[c] = 1
        A.append(eqn)
        A[c], A[-1] = A[-1], A[c]
    for r in range(c + 1, len(A)):
        d = gcd(abs(A[r][c]), abs(A[c][c]))
        m1 = A[r][c] // d
        m2 = A[c][c] // d
        for c2 in range(5):
            A[r][c2] = m1 * A[c][c2] - m2 * A[r][c2]

가우스 소거법을 사용하여 계수 행렬 A를 행 사다리꼴 형태로 변형합니다.

  
for r in range(4, len(A)):
    if A[r][4] != 0:
        print("No solution.")
        sys.exit()

행 사다리꼴 형태로 변형한 후, 모순이 발생하면 해가 없는 경우이므로 “No solution.”을 출력하고 프로그램을 종료합니다.

  
x4 = Fraction(A[3][4], A[3][3])
x3 = reduce(Fraction(A[2][4], 1) - A[2][3] * x4) / A[2][2]
x2 = reduce(Fraction(A[1][4], 1) - A[1][3] * x4 - A[1][2] * x3) / A[1][1]
x1 = reduce(Fraction(A[0][4], 1) - A[0][3] * x4 - A[0][2] * x3 - A[0][1] * x2) / A[0][0]

역대입법을 사용하여 변수 x1, x2, x3, x4의 값을 구합니다.

  
for r in range(R):
    row = []
    for c in range(C):
        here = reduce((1 - r - c + r * c) * x1 + (r - r * c) * x2 + (c - r * c) * x3 + (r * c) * x4)
        if here.denominator == 1:
            row.append(f"{here.numerator}")
        else:
            row.append(f"{here.numerator}/{here.denominator}")
    print(" ".join(row))

구한 해를 이용하여 격자의 빈 칸을 채우고, 결과를 출력합니다.
각 칸의 값은 기약분수 형태로 출력합니다.

전체 코드

  
import sys
from fractions import Fraction
from math import gcd

def reduce(f):
    if f.denominator < 0:
        f = Fraction(-f.numerator, -f.denominator)
    d = gcd(abs(f.numerator), abs(f.denominator))
    return Fraction(f.numerator // d, f.denominator // d)

input = sys.stdin.readline
R, C = map(int, input().split())
A = []
for r in range(R):
    line = input().split()
    for c in range(C):
        S = line[c]
        if S == ".":
            continue
        eqn = [0] * 5
        eqn[0] = 1 - r - c + r * c
        eqn[1] = r - r * c
        eqn[2] = c - r * c
        eqn[3] = r * c
        eqn[4] = int(S)
        A.append(eqn)

for c in range(4):
    for r in range(c, len(A)):
        if A[r][c] != 0:
            A[c], A[r] = A[r], A[c]
            break
    if c == len(A) or A[c][c] == 0:
        eqn = [0] * 5
        eqn[c] = 1
        A.append(eqn)
        A[c], A[-1] = A[-1], A[c]
    for r in range(c + 1, len(A)):
        d = gcd(abs(A[r][c]), abs(A[c][c]))
        m1 = A[r][c] // d
        m2 = A[c][c] // d
        for c2 in range(5):
            A[r][c2] = m1 * A[c][c2] - m2 * A[r][c2]

for r in range(4, len(A)):
    if A[r][4] != 0:
        print("No solution.")
        sys.exit()

x4 = Fraction(A[3][4], A[3][3])
x3 = reduce(Fraction(A[2][4], 1) - A[2][3] * x4) / A[2][2]
x2 = reduce(Fraction(A[1][4], 1) - A[1][3] * x4 - A[1][2] * x3) / A[1][1]
x1 = reduce(Fraction(A[0][4], 1) - A[0][3] * x4 - A[0][2] * x3 - A[0][1] * x2) / A[0][0]

for r in range(R):
    row = []
    for c in range(C):
        here = reduce((1 - r - c + r * c) * x1 + (r - r * c) * x2 + (c - r * c) * x3 + (r * c) * x4)
        if here.denominator == 1:
            row.append(f"{here.numerator}")
        else:
            row.append(f"{here.numerator}/{here.denominator}")
    print(" ".join(row))

이상으로 산술 직사각형 채우기 문제에 대한 풀이를 마치겠습니다. 감사합니다!

문제풀이, 알고리즘