1493. 수의 새로운 연산 (코딩테스트, SW Expert Academy)

문제 1493. 수의 새로운 연산

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b-QGqADMBBASw 

SW Expert Academy

 

---

나의코드 소요시간 : 57분 42초

def make_list(start_list, target):
    while start_list[-1] <= target:
        start_list.append(len(start_list)+start_list[-1])
    gap = (target-start_list[-2])
    x, y = 1+ gap, (len(start_list)-1) - gap
    return x, y
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    number_list = list(map(int, input().split()))
    number_list.sort()
    start_list = [1]
    x1, y1 = make_list(start_list, number_list[0])
    x2, y2 = make_list(start_list, number_list[1])
    x = x1+x2
    y = y1+y2
    
    while len(start_list) < (x+y):
        start_list.append(len(start_list)+start_list[-1])
    answer = start_list[-2] + (x-1)
    print(f"#{test_case} {answer}")
    # ///////////////////////////////////////////////////////////////////////////////////

---

검토

처음에는 2중 for문 + while문을 사용해서 해결하였다.

간단한 테스트 2개는 통과했으나 나머지 테스트에서 시간초과로 해결하지 못하여 규칙을 찾아야 했다.

해당 규칙을 찾는데는 오래걸리지 않았으나 리스트를 조금 복잡하게 써서 오류를 찾는데 시간을 많이썼다.

1
2	3
4	5	6
7	8	9	10
11	12	13	14	15

아이디어

1 -> 2,3 -> 4,5,6 이런식으로 생각해보자.

각 줄의 첫번째 값들의 x좌표는 무조건 1, y좌표는 n번째 줄이므로 (1,n) 좌표라 생각하면 된다.

옆으로 갈때 x좌표는 +1 y좌표는 -1 이기 때문에 좌표값들의 합산은 같은 줄에서는 모두 같다.

 

즉 (4,4) 좌표의 값을 찾고자 한다면? ->4+4 인 8이며 n-1을 한 7번째줄의 4번째 값을 출력하면 된다.

n에 1을 뺀 이유는 맨 첫번째 x값이 1로 고정되었기 때문에 1+n이 x+y값이 되기 때문이다.

 

즉 메인값들 (계차수열 형태를 가진다.)을 가진 리스트를 구하고자하는 값을 포함할 정도로 만든 후

좌표를 찾으면 된다.

 

내가 만든 코드는 메인 값들에서 두번째로 큰 수와 같은 줄에 찾고자하는 값이 있기 때문에 [-2]를 사용하게 되었다.