[python 백준 9358] 순열 접기 게임

📜 접근 방법

1. 양 끝의 수를 더하되 리스트의 갯수가 2개가 아닐 때까지 더한다.
2. 리스트의 갯수가 홀수일 경우 가운데 있는 수를 2번 더해야한다.
3. 리스트의 갯수가 2개일 경우 while문을 종료하고 숫자 비교후 출력

❌ 실패 코드 시간 초과

import sys

def fold(arr):
    new_arr = []

    i = 0
    j = len(arr) - 1
    while i <= j:
        new_arr.append(arr[i] + arr[j])
        i += 1
        j -= 1
    return new_arr


T = int(sys.stdin.readline())

for i in range(1, T + 1):
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    new_arr = arr
    while True:
        new_arr = fold(new_arr)
        if len(new_arr) == 2:
            break
    if new_arr[0] > new_arr[1]:
        print("Case #", i, ": Alice", sep="")
    else:
        print("Case #", i, ": Bob", sep="")

다른 분이 한걸 보니 재귀로 돌려서 위의 코드에서 재귀로 변경

 

✅ 정답 코드

import sys

def fold(arr):

    if len(arr) == 2:
        return arr

    new_arr = []
    i = 0
    j = len(arr) - 1
    while i <= j:
        new_arr.append(arr[i] + arr[j])
        i += 1
        j -= 1
    return fold(new_arr)


T = int(sys.stdin.readline())

for i in range(1, T + 1):
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    new_arr = arr
    while True:
        new_arr = fold(new_arr)
        if len(new_arr) == 2:
            break
    if new_arr[0] > new_arr[1]:
        print("Case #", i, ": Alice", sep="")
    else:
        print("Case #", i, ": Bob", sep="")

💡알게 된점
시간 초과가 났을 경우 문제에 따라 다르지만 해결 방안 중 하나인 재귀를 사용해봐야겠다.