SW Expert Academy 4881. 배열 최소 합

 

문제는 여기

한마디
분할된 것은 리스트인가 내 멘탈인가

 

 

 

 

def RSP(a, b): #가위바위보 관련 함수
    if num_list[a] == num_list[b]:
        return a
    if num_list[a] == 3 and num_list[b] == 1:
        return b
    if num_list[a] == 1 and num_list[b] == 3:
        return a
    if num_list[a] > num_list[b]:
        return a
    return b

def partition(arr): #팀 두개로 나누기 관련
    if len(arr)==1: #리스트 크기가 하나이거나 두개일때 그대로, 또는 가위바위보를 해서 리턴
        return arr
    elif len(arr) ==2:
        res = RSP(arr[0], arr[1])
        if arr[0] == res:
            return arr[0:1]
        else:
            return arr[1:]
    else:
        if len(arr)%2 ==0:
            left = arr[:len(arr)//2]
            right = arr[len(arr)//2:]
        else:
            left = arr[:len(arr)//2+1]
            right = arr[len(arr)//2+1:]
        return partition(partition(left) + partition(right)) #이부분 표현방법에서 애먹었다.

T = int(input())

for test_case in range(1, T + 1):
    N = int(input())
    num_list = list(map(int, input().split()))
    idx_list = [i for i in range(N)]
    result = partition(idx_list)
    print(result[0]+1)

 다 풀고 다른 사람들 코드를 봤는데 내거 너무 길더라ㅎㅎㅎ...

left, right 자리에 아예 다음 함수를 넣어서 편리하게 한 코드들도 있었다.

분할 정복은 난..정말 너무 힘들다..DP도 힘들다....