[백준 python] 10819번 차이를 최대로 -재귀, 순열 풀이

[백준 python] 10819번 차이를 최대로 -재귀, 순열 풀이

레벨: 실버 1

언어: python

---

문제풀러가기

📑풀이 과정

재귀와 순열 각 다른 방식으로 풀어 보았다.

1번 재귀

n = int(input())
in_list = list(map(int ,input().split()))
visited = [False]*n
answer = 0
def sol(li):
  global answer
  if len(li) == n:
    total = 0
    for i in range(n-1):
      total += abs(li[i]- li[i+1])
    answer = max(answer, total)
    return

  for i in range(n):
    if not visited[i]:
      visited[i] = True
      li.append(in_list[i])
      sol(li)
      visited[i] = False
      li.pop()

sol([])
print(answer)

입력으로 숫자 배열은 받는데 이미 계산한 숫자를 확인하기 위해 visited 배열을 만들었다.
그리고 매개변수로 배열을 넘겨주고 배열에 숫자를 하나씩 넣고 다시 sol 함수를 호출한다.
매개변수로 넘긴 배열의 길이가 n과 같으면 문제에서 주어진 계산 방식으로 계산한다.
계산 결과가 최대 값인지 확인 후 최대값이면 answer에 저장하고 리턴한다.

지금 이 풀이를 작성하다 보니 visited 배열을 구지 사용하지 않고 매개변수 안에 포함 되어 있는지 확인해도 같은 동작을 할 것으로 예상된다. 이 부분은 다시 작성 해보도록한다.

2번 순열

from itertools import permutations

n = int(input())
arr = list(map(int ,input().split()))

permu = list(permutations(arr, n))
def calculator(li):
  total = 0
  for i in range(len(li)-1):
    total += abs(li[i]-li[i+1])
  return total

answer = -1e9
for li in permu:
  answer = max(answer, calculator(li))

print(answer)

이 문제는 순열을 사용해서 손 쉽게 풀 수 있다.
최소 숫자도 8까지여서 시간적으로도 충분하다
순열로 들어오는 수의 모든 경우를 다 뽑아서 문제에서 주어진 계산 방식으로 계산하고 최댓값을 만들면 된다.

---