BOJ 9094 - 수학적 호기심

문제

백준 온라인 저지 - 9094번

풀이 과정

가능한 모든 조합을 만들어본 다음 주어진 조건을 만족하는 조합의 개수를 구하는 문제입니다.

처음에 a 와 b 의 조합의 개수가 10000개를 넘지 않기 때문에 단순 조합개수를 만들어서 시도했는데

테스트 케이스의 개수 T 를 고려하지 못해서 시간 초과가 발생했습니다.


이를 위해 a, b, m 을 상태변수로 하는 메모이제이션을 적용해서 중복된 계산을 줄이는 방식으로 해결할 수 있습니다.

코드

import sys


def solution():
    ret = 0

    for a in range(1, n):
        for b in range(a + 1, n):
            if memo[a][b][m] != -1:
                ret += memo[a][b][m]
                continue

            numerator, denominator = (a**2 + b**2 + m), (a * b)

            if numerator % denominator == 0:
                ret += 1
                memo[a][b][m] = 1
            else:
                memo[a][b][m] = 0

    return ret


if __name__ == '__main__':
    T = int(input())
    memo = [[[-1 for _ in range(101)] for _ in range(101)] for _ in range(101)]

    for _ in range(T):
        n, m = list(map(int, sys.stdin.readline().split()))
        answer = solution()

        print(answer)