SWEA 4112 - 이상한 피라미드 탐험

이상한 피라미드 탐험

---

◎ Problem Definition

※ 출처 : SW Expert Academy

SW Expert Academy

 

◎ Problem Analysis

1. Problem Type

• Implementation

2. Planning

피라미드 형태로 적층된 숫자 피라미드를 2D list로 구현하자. 

최소 이동 횟수를 계산한다. 

• 세로 방향 이동 횟수 : 두 수의 column index 차이 
• 가로 방향 이동 횟수 : 두 수의 row index 차이로 생각할 수 있지만, 한 layer당 1만큼의 차이는 바로 접근이 가능하다.   
  • 예를 들어 [2,1] 위치의 '5'와 [1,0]의 '2'는 가로 방향으로 1과 0의 인덱스를 갖으며, 두 수의 횡방향 거리는 1-0 = 1 만큼 차이가 난다. 하지만, 피라미드형 적층 구조에서는 횡방향 거리 '0으로 바로 접근이 가능하다.                                 
  • dist_x = max(0, abs(n1_x - n2_x) - dist_y)

 

◎ Implementation

1. Solution (Trial #1)

# ---------------------------------------------------------------
# SW Expert Academy 4112, 이상한 피라미드 탐험
# date : Feb. 4th, 2022
# writer : Elie H
# ---------------------------------------------------------------
### 1000가지 case 중 약 420 case만 통과.. 흥, 칫, 뿡!!! 

pyramid = []


def set_pyramid(now, tar):
    '''
    피라미드 형태로 적층된 숫자의 배열을 구조화 한다.
    원소 1개 (1) → 원소2개 (2,3) → 원소 3개 (4,5,6), ... ,
    '''
    n = 1
    itr = 1
    N = now if now >= tar else tar # N = max(now, tar)
    while N :  # N개 원소 적층하기
        data = [i for i in range(n, n+itr)]
        n = n+itr
        itr += 1
        pyramid.append(data)
        if data[-1] >= N:
            break
    return

def find_idx(num):
    '''
    pyramid 배열 내 num의 위치 index, (i, j)를 찾는다.
    '''
    for i in range(len(pyramid)) :
        if num in pyramid[i]:
            j = pyramid[i].index(num)
            return i, j
    return 0, 0

def cal_dist(now, tar):
    '''
    pyramid 배열 내 now -> tar 로 이동하기 위한 최소 이동 횟수를 계산한다.

    '''
    n1_x, n1_y = find_idx(now)
    n2_x, n2_y = find_idx(tar)

    dist_y = abs(n1_y - n2_y)
    dist_x = max(0, abs(n1_x - n2_x)-dist_y)

    return dist_x + dist_y

# Inputs : 
#     - T : Number of test (1 ≤ T ≤ 1,000)
#     - now, tar : current position, target position (1 ≤ now, tar ≤ 10,000)
T = int(input())
for t in range(T):
    count = 0 
    minji, tresure = list(map(int, input().split()))  # 현재 위치와 target pos 입력 
    set_pyramid(minji, tresure)
    count += cal_dist(minji, tresure)
    print(f'#{t+1} {count}')

 

◎ Conclusion

• 1000개의 test 중 약 420개의 case만 통과해서 Fail이다. 어디가 문제인지 아직 잘 모르겠다.
• 처음에는 BFS를 시도해봤지만, 함께 공부하는 팀원들과 토론 후 훨씬 간단하게 접근할 수 있다는 사실을 깨달았다. → 문제 분석을 더 꼼꼼히 하고, planning 단계에서 다양한 방법을 고민해보자. 
• np.where를 적용하여 index를 얻고 싶었지만, 코드 제출 단계에서 import numpy가 안된다는 사실을 알았다.  → 코딩테스트의 경우, 사용 가능한 라이브러리의 범위를 잘 알아야겠다. (미리 테스트해보자.)