[BruteForce]99클럽 코테 스터디 35일차 TIL + 백준/Bronze/9094. 수학적 호기심

[Bronze III] 수학적 호기심 - 9094

문제 링크

성능 요약

메모리: 32140 KB, 시간: 4588 ms -> 3797ms

분류

브루트포스 알고리즘, 수학

제출 일자

2024년 8월 27일 19:00:11

문제 설명

두 정수 n과 m이 주어졌을 때, 0 < a < b < n인 정수 쌍 (a, b) 중에서 (a²+b²+m)/(ab)가 정수인 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, n과 m이 주어진다. 두 수는 0보다 크고, 100보다 작거나 같다.

출력

각 테스트 케이스마다 문제의 조건을 만족하는 (a, b)쌍의 개수를 출력한다.

 

 

<내코드>

if __name__ == "__main__":

    case_number = int(input())

    case = []
    for _ in range(case_number):
        case.append(list(map(int,input().split())))

    def numerator(a, b, m):
        return a**2 + b**2 + m # 계속 ^ 이걸로 쉬프트연산으로 함


    for n, m in case:
        count = 0
        for a in range(1,n):
            for b in range(a + 1, n):
                if numerator(a,b,m) % (a*b) == 0:
                    count += 1
        print(count)

- (a2+b2+m) / (ab)가 정수

=> 두개의 값을 나누었을 때 결과가 정수인것은 곧 나누어 떨어진다는것을 알게되었음

 

- 처음에는 조합으로 생각을 했다가, 문제의 조건을 착각하고 엄밀하게 a,b의 크기가 나누어져야한다고 생각해서 직접 탐색을 선택함

=> 하지만 문제에는 특별한 이런 조건이 없었음 결국 조합으로 풀기 가능함

 

- 제곱연산을 ^ 비트 연산자로 모르고 이용하게 됨

from itertools import combinations

if __name__ == "__main__":

    case_number = int(input())
    def count_valid_pairs(n, m):
        count = 0
        for combo in combinations(range(1,n), 2):
            numerator = combo[0]**2 + combo[1]**2 + m
            mother = (combo[0] * combo[1])
            if numerator % mother == 0:
                count += 1
        print(count)

    for _ in range(case_number):
        l = list(map(int, input().split()))
        count_valid_pairs(l[0], l[1])

- 4588ms -> 3796ms 으로 줄어듬

조합으로 보다 쉽게 해결이 가능함

첫번째 조합은 두개의 값이 같은것이 나올 수 없음

두번째 a,b의 값중 누가 뚜렷히 구분되어야하는것은 없음

 

<모범사례>

 

from itertools import combinations

def count_valid_pairs(n, m):
    count = 0
    for a, b in combinations(range(1, n), 2):
        sum_squares = a**2 + b**2 + m
        product_ab = a * b
        if sum_squares % product_ab == 0:
            count += 1
    return count

if __name__ == "__main__":
    case_number = int(input())
    for _ in range(case_number):
        n, m = map(int, input().split())
        print(count_valid_pairs(n, m))

 

 

 

<보충학습>

관련 문제 기초 개념 연습풀기