20200811 // 삼성 SW Expert 아카데미 문제 // 1493
2020. 8. 11. 12:56ㆍProgramming/SW Expert Academy
삼성 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 빠르게 나왔다.
'Programming > SW Expert Academy' 카테고리의 다른 글
20200817 // 삼성 SW Expert 아카데미 문제 // 10580 (0) | 2020.08.17 |
---|---|
20200813 // 삼성 SW Expert 아카데미 문제 // 1238 (0) | 2020.08.13 |
20200810 // 삼성 SW Expert 아카데미 문제 // 6019 (0) | 2020.08.10 |
20200807 // 삼성 SW Expert 아카데미 문제 // 1486 (0) | 2020.08.07 |
20200806 // 삼성 SW Expert 아카데미 문제 // 5213 (0) | 2020.08.06 |