[Python, 파이썬] SWEA 1493. 수의 새로운 연산

 

 

위 그림과 같이 대각선 순서로 점에 수를 붙인다.

&은 수가 주어질 때 그 위치를 찾는 연산이며, 반대로 #은 위치가 주어질 때 수를 찾는 연산이다.

 

p★q는 #(&(p)+&(q))이라 할때, 와 수에 대한 새로운 연산 ★를 구현해보는 문제.

 

 

 

[코드]

---

def startIndex(): # 시작 번호 배열 구하기
    
    A = [1 for i in range(400)] # 시작 번호 배열
    for i in range(1, 400):
        
        A[i] = (A[i-1]+i) # A 배열 값 채우기 

    return A
    

def And(n): # (연산 & : 번호-> 위치)
    
    for i in range(len(A)):
    
        if(A[i] > n):
            x, y = (1, i) # 대각선의 시작점
            diff = n - A[i-1] # 차이 구하기
            break

    return (1+diff, i-diff) # 좌표 return

def Hash(x, y): # (연산 # : 위치 -> 번호)
    
    index = A[x+y-2] # 위치가 해당하는 대각선의 시작 번호

    return index+(x-1) # 시작번호 + diff
    

def star(p, q): # 새로운 연산 ★
    
    x1, y1 = And(p) # p의 & 연산
    x2, y2 = And(q) # q의 & 연산

    answer = Hash(x1+x2, y1+y2) # &(p)+&(q)의 #연산

    return answer

T = int(input()) # 테스트케이스 개수 T
A = startIndex() # 대각선의 시작번호 구하기

for test_case in range(1, T+1):

    p, q = map(int, input().split()) # (p, q)

    # ★ 연산하기
    answer = star(p, q)               

    print("#%d %d" %(test_case, answer))

 

 

 

 

[문제풀이]

---

 

내가 집중한 건 대각선의 시작점이다.

 

 

이 대각선의 시작점은 1부터 시작해서 대각선의 길이, 즉 i를 계속해서 더해나가는 규칙이 있었다.

이를 점화식으로 만들어 대각선들의 시작점의 배열을 구한다.

A[i] = (A[i-1]+i) # A 배열 값 채우기 

 

이때 배열의 크기는 충분히 크게 해야 한다....

한 200개면 괜찮겠지 싶어서 만들었다가 자꾸 에러떴다.

그리고 이 대각선들의 시작점들을 통해 #와 & 연산을 구현했다.

 

 

● & 연산

 

 

수를 받아 위치를 구하는 & 연산의 경우 위와 같은 방식으로 구한다.

숫자가 시작하는 대각선의 번호를 찾는다.

그럼 그 위치의 시작점은 (1, i+1)가 된다.

 

그 후 찾는 번호 - 시작 번호의 diff를 시작 번호에 각각 연산해주면 위치를 찾을 수 있다.

 

 

● # 연산

 

index = A[x+y-2] # 위치가 해당하는 대각선의 시작 번호

 

위치를 받아 수를 연산하는 # 연산의 경우엔 대각선이 위치한 점들의 합은 동일하다는 점을 이용했다.

그럼 (x, y)의 경우엔 (x+y)-2번째 위치의 값이 대각선의 시작점의 수다.

return index+(x-1) # 시작번호 + diff

 

그럼 그 시작점 수 index에 x에 더해진 diff값을 더해 수를 찾아주면 된다.

 

이렇게 차례로 &와 # 연산을 마친 새로운 연산 ★을 통해 답을 구해주면 끝!