[SWEA / PYTHON] 1493. 수의 새로운 연산

result = []

T = int(input())

for case in range(1, T+1):
    p, q = map(int, input().split())

    arr = list([1] * (max(p, q) + 3))

    
    for j in range(1, max(p, q) + 3):
        arr[j] = arr[j-1] + j
        if arr[j] > max(p, q):
        	arr = arr[ : j + 1 ]
            break

    position_p = 0
    position_q = 0
    for i in range(max(p, q)):
        if p < arr[i+1]:
            position_p = [i+1, p - arr[i] + 1]
            break
    
    for i in range(max(p, q)):
        if q < arr[i+1]:
            position_q = [i+1, q-arr[i] + 1]
            break
    
    position_target = [position_p[0]+position_q[0], position_p[1]+position_q[1]]


    result.append(f"#{case} {arr[position_target[0]] + position_target[1]-1}")


for _ in result:
    print(_)

풀이.

우선 그림의 좌표 형식을 우리가 사용하기 쉽게 배열 형태로 변환한다

이런 식으로 좌표를 눕혀서, 코드 내에서 사용하기 쉽게 만들자.
우리는 모든 좌표의 값을 알 필요가 없다.
모든 좌표 값을 배열로 만들려고 하면, 메모리 초과나 혹은 시간이 엄청나게 오래 걸릴 것이다.
따라서, 맨 첫번째 값만 알면, 원하는 위치 좌표에 무슨 값이 들어있을 지 알 수 있다.

Input 으로 6679 9828 를 입력받으면
y 값이 1 ( 배열에서는 0 )인 구간에서, 9828 보다 더 큰 값이 나오면 배열 생성을 중단한다.
즉 x 의 좌표는 중단 점에서 -1을 해주면 되는 것이고, y의 좌표는 p 혹은 q - arr[x-1] - 1 이 되는 것이다.

불필요한 연산을 확 없애버린..
생각보다 이 문제에 시간을 많이 할애 했다.
해결한 만큼 생각의 리프레쉬가 됐다.