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

문제 설명 

(출처: https://swexpertacademy.com/)

2차원 평면 제 1사분면 위의 격자점 (x,y)에 위 그림과 같이 대각선 순서로 점에 수를 붙인다.

 

점 (x,y)에 할당된 수는 #(x,y)로 나타낸다.
예를 들어 #(1,1) = 1, #(2,1)=3, #(2,2) = 5, #(4,4) = 25이다.

 

반대로 수 p가 할당된 점을 &(p)로 나타낸다.
예를 들어 &(1) = (1,1), &(3) = (2,1), &(5) = (2,2), &(25) = (4,4)이다.

두 점에 대해서 덧셈을 정의한다. 점 (x,y)와 점 (z,w)를 더하면 점 (x+z, y+w)가 된다.
즉, (x,y) + (z,w) = (x+z, y+w)로 정의한다.

우리가 해야 할 일은 수와 수에 대한 새로운 연산 ★를 구현하는 것으로, p★q는 #(&(p)+&(q))으로 나타난다.
예를 들어, &(1)=(1,1), &(5) = (2,2)이므로, 1★5 = #(&(1)+&(5)) = #((1,1)+(2,2)) = #(3,3) = 13이 된다.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 두 정수 p,q(1 ≤ p, q ≤ 10,000)가 주어진다.

[출력]
각 테스트 케이스마다 ‘#t’(t는 테스트 케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 각 테스트 케이스마다 p★q의 값을 출력한다.

 

풀이과정

각 그룹의 규칙성을 찾아야 한다. 

<그룹별 시작점 & (x,y)좌표>

그룹 1	1 = 1	(1,1)
그룹 2	2  = 1 + (1)	(1,2)
그룹 3	4 = 1 + (1 + 2)	(1,3)
그룹 4	7 = 1 + (1 + 2 + 3)	(1,4)
그룹 5	11 = 1 + (1 + 2 + 3 + 4)	(1,5)
그룹 6	16 = 1 + (1 + 2 + 3 + 4 + 5)	(1,6)
...	...	...

 

• group = 그룹 번호 변수
• 시작점  start_num = 1 + group * (group - 1) / 2

# 예시 

p = 13 일 때, 11보다는 크고 16보다는 작으니 그룹5에 속한다. 

이때 11은 1 + 5*(5-1)/2 => 즉, 그룹번호 5가 도출가능.

=> 시작점은 (1,5)임을 이미 안다. 

=> 좌표구하기: |p-시작값| = |13 -11| = 2 만큼 시작점 (1+2, 5-2) 해주면 => (3,3)이 13의 좌표임.

=> 값 구하기: 

 

 

1. 특정 값 p의 그룹 찾기

• 그룹의 시작값 <= p <= 그 다음 그룹의 시작값 
• 어떤 그룹의 시작값보다 p값이 작다면, 그 전 그룹에 p가 속한다고 볼 수 있다. 
• 리턴값: p가 속하는 그룹의 (시작점의 y좌표, 시작값)

def getGroup(num):
    for y in range(200):
        start_num = 1 + y*(y-1)/2
        if num < start_num: 
            return y-1, 1+(y-1)*(y-2)/2

 

2. 특정 값 p의 좌표 찾기

• start_y, start_num = p가 속하는 그룹 시작점의 y좌표, 시작값 
• dxdy: 시작값과 p의 차이만큼 좌표값도 차이난다는 점에서 계산
• => 시작점 (1, start_y)에서 (1+dxdy, start_y - dxdy) 해준다.

def getXY(num):
    start_y, start_num = getGroup(num)
    #print('num{} startY{} startNum{}'.format(num, start_y, start_num))
    dxdy = abs(start_num - num) 
    x = 1+dxdy
    y = start_y-dxdy
    #print('\tX{} Y{}'.format(x, y))
    return x,y

3. 좌표에 해당하는 값 구하기 

• 좌표(x,y)가 속한 그룹을 찾는다. => x-1 = 시작점y좌표 - y
• 시작점y좌표 = 그룹번호 
• 해당 그룹의 시작값을 구하고, dxdy만큼 더하면 된다. 

def getNum(rx,ry):
    dxdy = rx - 1
    group = ry + dxdy  # 시작점의 y좌표이자 그룹번호이다.
    start_num = 1 + group*(group-1)/2 
    answer = start_num + dxdy
    return answer

## 전체 코드 

def getGroup(num):
    for y in range(200):
        start_num = 1 + y*(y-1)/2
        if num < start_num: 
            return y-1, 1+(y-1)*(y-2)/2
        
def getXY(num):
    start_y, start_num = getGroup(num)
    #print('num{} startY{} startNum{}'.format(num, start_y, start_num))
    dxdy = abs(start_num - num) 
    x = 1+dxdy
    y = start_y-dxdy
    #print('\tX{} Y{}'.format(x, y))
    return x,y

def getNum(rx,ry):
    dxdy = rx - 1
    group = ry + dxdy 
    start_num = 1 + group*(group-1)/2
    answer = start_num + dxdy
    return answer

for jc in range(1,T+1):
    p, q = map(int, input().split())
    
    px, py = getXY(p)
    qx, qy = getXY(q)
    
    #print(px, py, qx, qy)
    rx, ry = px+qx, py+qy 
    print('#{} {}'.format(jc, getNum(rx, ry)))