Algorithm python) 백준 10819번 차이를 최대로

문제 링크 : https://www.acmicpc.net/problem/10819

모든 경우의 수를 따져보는 조합문제이다.
라이브러리 itertools의permutation를 사용하여 간편하게 풀 수 있지만
라이브러리를 사용하지 않고 애를 먹었던 부분을 기록으로 남긴다.

from itertools import permutations

n = int(input())
number = list(map(int, input().split()))
maxNumber = 0

permutationNumber = permutations(number, n)

for i in permutationNumber:
    ans = 0
    for j in range(1, len(i)):
        ans += abs(i[j-1] - i[j])
    maxNumber = max(maxNumber, ans) 

print(maxNumber)

n = int(input())
check = [True] * n
num = list(map(int, input().split()))

inner = []
ans = []
def permutation(depth, n):
    if(depth == n+1):
        ans.append((inner))
        return 
    for i in range(n):
        if(check[i]):
            check[i] = False
            inner.append(num[i])
            permutation(depth+1, n)
            inner.pop()
            check[i] = True

permutation(1, n)
print(ans)

위에 코드는 정답을 출력하는 코드는 아니다. 중간 과정 중에서

if(depth == n+1):
        ans.append((inner))
        return 

재귀함수를 빠져나오는 블록에서 조합된 n개의 숫자가 제대로 append되는지 확인하는 과정이다.

ans를 출력하니 빈 리스트가 출력된다.

if(depth == n+1):
        ans.append(list(inner))
        return 

list(inner)로 바꿔줘야한다.
파이썬 기초지식이 부족하다

n = int(input())
check = [True] * n
num = list(map(int, input().split()))

inner = []
ans = []
def permutation(depth, n):
    if(depth == n+1):
        ans.append(sum(abs(inner[k-1] - inner[k]) for k in range(n-1)))
        return 
    for i in range(n):
        if(check[i]):
            check[i] = False
            inner.append(num[i])
            permutation(depth+1, n)
            inner.pop()
            check[i] = True

permutation(1, n)

print(max(ans))

재귀함수를 사용하여 모든 경우의 수를 가져오는 것인데
지난번에 풀었던 백준 문제 : N과 M(1) 문제 핵심은 둘다 동일한 것을 알 수 있었다. 알고리즘 문제를 풀다보면, 겉포장은 달라도 핵심 부분은 같은 경우가 반복되는 것을 느낀다.