문제

상근이는 선영이와 함께 게임을 하고 있다. 먼저, 상근이는 두 양의 정수 A와 B를 고른다. (1 ≤ B ≤ A ≤ 500) 그 다음, 선영이는 상근이가 고른 수를 맞춰야 한다.

상근이는 선영이에게 다음과 같은 힌트를 주었다.

A의 제곱은 B의 제곱보다 N만큼 커 (1 ≤ N ≤ 1,000)

위의 힌트 조건을 만족하는 A와 B 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

상근이의 힌트 조건을 만족하는 (A,B) 쌍의 개수를 출력한다.

solved 기준으로 브론즈3, 대체로 난이도가 약한 문제. 처음 봤을 때 막막했다. 깔끔한 방법이 떠오르지 않아서. 결국은 브루트포스(완전탐색) 알고리즘으로 우직하게 푸는 걸로.

처음부터 n의 최대값까지 제곱수를 리스트로 생성. 두 번째 원소부터 차례로 그 앞 제곱수들을 하나씩 빼 본다. 차이가 n이 되면 cnt += 1 해주었다. 마지막으로 cnt를 출력.

그러면 아래 코드가 나온다.

p = [i**2 for i in range(1, 501)]
n = int(input())
cnt = 0
for i in range(1, 500):
    for j in range(0, i):
        if p[i] - p[j] == n:
            cnt += 1
print(cnt)

이것까진 그리 어렵진 않다.

그런데 문제를 맞힌 파이썬 코드를 둘러보다 특이한 코드 하나를 발견. 오, 이렇게도 풀 수 있구나.

n = int(input())
cnt = 0
for i in range(1, n+1):
    if n % i == 0 and (n//i+i)%2 == 0: # 대를 이루는 약수끼리 (예: 15면 1-15, 3-5) 더한 값이 짝수이면 cnt += 1
        cnt += 1
print(cnt//2) # 쌍의 수를 묻는 것이니 최종 cnt 나누기 2 출력.

이것이 어떻게 주어진 숫자 n만큼 차이나는 제곱수의 쌍 수가 되는지는 잘 모르겠다. 구글링하다 찾은 건 이것. 소인수분해를 이용해 약수 구하기, 약수 개수 구하기. 이것과 관련 있는지는 잘 모르겠다. 아무튼, 된다.

[문제 보기]