[PS] [Baekjoon] 9464. 직사각형 집합

https://www.acmicpc.net/problem/9464

 

언어 : 파이썬 (Python)

시작 : 2024.12.20 20:40

종료 : 2024.12.20 21:30

티어 : Gold III

비고 : 2013 Daejeon ICPC Regional J번

 

태그 :

수학, 그리디

 

문제 해석

 

$x > y > 0$인 정수 $(x, y)$로 $(a, b, c)$ 를 구성하면 되는 문제.

$a=2xy$ $b=x^2-y^2$ $c=x^2+y^2$

 

문제에 수학이 포함되어 살짝 어지러운 편이지만,

간단히 요약하면 (3, 4, 5) 나 (5, 12, 13) 처럼 세 개의 정수로 직각삼각형을 만들 수 있으면 된다.

 

철사의 길이 $L$이 주어지면, $a$와 $b$로 만들 수 있는 직사각형의 최대 개수를 구하는 문제.

직사각형은 $2a+2b$길이로 만들어진다.

 

유의할 점은 3가지 정도 있다.

1) $a$와 $b$의 최대공약수는 1이어야한다. 문제에는 적혀있지 않지만 구현하다보면 자연스럽게 받아들여질 것.

2) 항상 $a>b$꼴이 되진 않는다. 예를 들어 x=2, y=1이면 $(4, 3, 5)$ 가 나온다.

3) 길이 $L$을 꼭 맞춰야하는 건 아니다. 즉, 철사를 좀 남겨도 된다.

풀이

 

직사각형의 최대 개수를 구하는 문제이므로,

직사각형 하나를 만드는데 적은 양의 철사를 쓴다면 그게 최적의 해일 것이다.

굳이 $L$을 다 써야하는 것도 아니므로.

 

따라서 모든 $2a+2b$ 꼴로 나오는 철사 길이를 구해 list에 넣고,

해당 list를 오름차순으로 정렬하여 길이 $L$에 도달할 때까지 더해가는 while을 돌리면 그만일 것이다.

 

 

핵심은 피타고리안 트리플 $(a, b, c)$를 구하는 파트다.

길이가 1백만 이하이므로, 가능한 $L$은 백만 언저리까지만 구하면 좋을 것이다.

따라서 모든 x와 y에 대해 이중 탐색을 돌려주는 풀이법을 구상했다.

 

그러나 (8, 6, 5) 와 같이 GCD가 1이 아닌 경우는 배제해야하므로 GCD를 구하는 것도 핵심이지만,

난 그냥 귀찮아서 fraction 라이브러리를 썼다.

Fraction(4, 3) = Fraction(8, 6)이다.

 

코드

 

풀이 1) 성공, 600ms

import sys
from fractions import Fraction

input = sys.stdin.readline

T = int(input())

contains = set()
length_list = []

for x in range(1, 500):
    for y in range(1, x):

        a = 2 * x * y
        b = x ** 2 - y ** 2
        c = x ** 2 + y ** 2

        f = Fraction(max(a, b), min(a, b))
        if f in contains:
            continue

        if a ** 2 + b ** 2 == c ** 2:
            length_list.append(2 * (a+b))
            contains.add(f)

length_list.sort()

for _ in range(T):
    _sum = 0
    ans = 0
    i = 0

    L = int(input())
    while _sum + length_list[i] <= L:
        _sum += length_list[i]
        i += 1
        ans += 1

    print(ans)