이얏차 이제 브루트포스 실버 문제는 풀 수 있을 것 같다!

1. 내 풀이 - 성공

import sys
from itertools import permutations
input = sys.stdin.readline

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

maxSum = -801
for comb in permutations(a, n):
    sum = 0
    for i in (range(1, len(range(n)))):
        sum += abs(comb[i-1] - comb[i])
    maxSum = max(sum, maxSum)

print(maxSum) 

이번에도 브루트포스로 한 번 풀어봤다. 풀이 자체는 쉬우니 설명은 패스!

2. 다른 풀이 - DFS

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)

풀이 출처: https://wonyoung2257.tistory.com/77

예전에는 DFS의 visited과 왜 필요한지 몰랐는데 이제는 이해하겠다! 음 ... 설명을 하자면 브루트포스의 경우에는 이미 가능한 한 경우의 수를 모두 구해놓고 연산을 하는데, (permutation이든, combination이든) DFS의 경우에는 내가 이 값을 이전에 처리 했는지 안했는지를 컴퓨터는 모르니까 이를 알려주기 위해 사용하는 것 같다.

그리고 만약 combination과 같은 itertool을 사용할 수 없는 코테의 경우... 라면... 이렇게 DFS로 모든 경우의 수를 만들어줘야겠구나라는 생각도 들었다.

3. 마치며

예전에 포기했던 실버 문제를 도전해보겠다 ...! 과연 ... 순도 100%로 풀어낼 것인지 ...