문제 개요
네 개의 숫자 a, b, c, d가 주어졌을 때, 다음 방정식을 만족하는 정수 쌍 (x, y)의 개수를 구하는 프로그램을 작성해야 합니다.
x² + y² = a·x + b·y
단, x는 [1, c] 범위, y는 [1, d] 범위 안에 있어야 합니다.
예를 들어 입력이 a = 2, b = 3, c = 2, d = 4라면 출력은 1이 됩니다. 조건을 만족하는 유일한 쌍이 (1, 1)이기 때문입니다.
접근 방법
모든 (x, y) 조합을 완전 탐색하는 대신, 주어진 x마다 y에 대한 이차방정식을 풀어 유효한 해의 개수를 세는 방식이 훨씬 효율적입니다. 방정식을 y에 대해 정리하면 다음과 같습니다.
y² − b·y + x(x − a) = 0
이 이차방정식의 판별식은 D = b² − 4x(x − a)입니다. 정수 해가 존재하려면 D가 완전제곱수여야 하고, 근의 공식 y = (b ± √D) / 2에서 분자가 짝수여야 합니다. 마지막으로 계산된 y가 [1, d] 범위에 속하는지만 확인하면 됩니다. 구체적인 단계는 다음과 같습니다.
- ans := 0으로 초기화합니다.
- x를 1부터 c까지 반복합니다.
- l := x × (x − a)
- det2 := b² − 4l (판별식)
- det2가 0이고 b가 짝수이며 1 ≤ ⌊b/2⌋ ≤ d이면 중근 하나가 유효하므로 ans를 1 증가시키고 다음 반복으로 넘어갑니다.
- det2가 0보다 크면 det := √det2의 정수 부분을 구합니다.
- det² == det2이고 (b + det)가 짝수라면 두 근이 모두 정수이므로, (b + det)/2와 (b − det)/2가 각각 [1, d] 범위에 있는지 확인하고 해당되면 ans를 증가시킵니다.
- 반복이 끝나면 ans를 반환합니다.
구현 예제
다음 파이썬 코드를 통해 더 잘 이해할 수 있습니다. 부동소수점 오차를 피하기 위해 제곱근 계산 시 round를 사용한 점에 주목하세요.
def solve(a, b, c, d):
ans = 0
for x in range(1,c+1):
l = x*(x-a)
det2 = b*b - 4*l
if det2 == 0 and b%2 == 0 and 1 <= b//2 <= d:
ans += 1
continue
if det2 > 0:
det = int(round(det2**0.5))
if det*det == det2 and (b+det) % 2 == 0:
if 1 <= (b+det)//2 <= d:
ans += 1
if 1 <= (b-det)//2 <= d:
ans += 1
return ans
a = 2
b = 3
c = 2
d = 4
print(solve(a, b, c, d))입력
2, 3, 2, 4
출력
1
복잡도 분석
이 알고리즘은 x 값마다 상수 시간 연산만 수행하므로 시간 복잡도는 O(c)입니다. 가능한 모든 (x, y) 조합을 확인하는 완전 탐색 방식의 O(c × d)보다 훨씬 빠르며, 특히 c와 d가 클 때 그 차이가 두드러집니다. 공간 복잡도는 추가 배열 없이 몇 개의 변수만 사용하므로 O(1)입니다.