20200811 // 삼성 SW Expert 아카데미 문제 // 1493

삼성 SW Expert 아카데미 1493번 "수의 새로운 연산" 문제입니다.

from cmath import *
TC = int(input())   
ans = []
for tc in range(1, TC + 1):
    k = "#"+str(tc) + " "
    p, q = map(int, input().split())
    x1, y1, x2, y2 = 0, 0, 0, 0
    for i in range(1,10000):
        y = 3-2*i
        l = pow((2*i-3)*(2*i-3) - 4 * (i**2 - i + 2 - 2 * p),0.5)
        y += l
        y /= 2
        if y.is_integer():
            x1 = i
            y1 = int(y)
            break
     
    for i in range(1,10000):
        y = 3-2*i
        l = pow((2*i-3)*(2*i-3) - 4 * (i**2 - i + 2 - 2 * q),0.5)
        y += l
        y /= 2
        if y.is_integer():
            x2 = i
            y2 = int(y)
            break
     
    x3 = x1 + x2
    y3 = y1 + y2
    n = (x3**2 + x3)//2 + (y3**2 - y3)//2 + (y3-1)*(x3-1)
    k += str(n)
    ans.append(k)
for e in ans:
    print(e)

이 문제는 수학 문제라고 접근하면 돌아가는 시간이 짧아진다.

 

x축은 1, 3, 6, 10, ...인 각 항의 차이가 1씩 늘어나는 계차수열

 

y축은 1, 2, 4, 7, ...인 각 항의 차이가 1씩 늘어나는 계차수열이다.

 

(x,y)와 매칭되는 값 D = (x^2 + x) / 2 + (y^2 - y) / 2 + (y-1)(x-1) 이다.

 

그런데 역으로 D를 이용해서 구해야 하므로 저 식을 y에 대한 식으로 바꿔야 한다.

 

y에 대한 이차식으로 바꾼 후 근의 공식을 사용하면

 

y = (3-2x+((2x-3)^2-4(x^2-x+2-2D))^(1/2))/2

 

x, y는 항상 정수이므로 x를 1부터 for문을 돌려서 대입한다.

 

x를 넣었을 때, y의 값이 정수라면, 즉 is_integer() 함수를 사용해서 참일 경우 그 값을 사용

 

아닐 경우 반복문 계속 진행으로 한다. 이를 두 값에 적용하여 각각의 x,y 값을 도출한 후에

 

문제에 나온 덧셈 연산을 이용해서 새로운 x, y값을 구하고 이를 다시 위의 D를 구하는 식에 넣으면 갑이 나온다.

 

다른 사람이 어떻게 풀었는지는 모르겠지만 이 방식으로 푸니까 Python 언어를 사용한 사람들 보통 시간대보다

 

100ms 빠르게 나왔다.