[Python][백준] 10819. 차이를 최대로 / 브루트포스,백트레킹(S2)

🗒️파이썬 코드 풀이

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().split()))
visited = [0] * N
mx = -1e10

def dfs(n, rs):
    global mx
    if n >= N:
        sum = 0
        for i in range(N - 1):
            sum += abs(rs[i] - rs[i + 1])
        mx = max(mx, sum)
        return

    for i in range(N):
        if not (visited[i]):
            visited[i] = 1
            rs.append(lst[i])
            dfs(n + 1, rs)
            visited[i] = 0
            rs.pop()


dfs(0, [])
print(mx)

 

1. N의 범위는 8까지이다. 이런 경우는 재귀함수를 생각한다.

 

2. 먼저 lst, 방문리스트, 최대값을 생성한다. 

 

3. dfs의 매개변수로 n과 rs 리스트를 준다.

여기서  n은 depth이고, 이것은 재귀함수의 종료를 제어해준다.

 

4. dfs에서 N 크기의 반복문을 만들고, 만들어질 수 있는 모든 조합을 만든다.

🚨 (1) 방문 처리를하고, (2)  rs 리스트에 새로운 lst[i]를 넣고
(3)dfs 함수를 호출한다. 그 다음 꼭 (4) 방문 해제를하고
(5) 방금 넣은 lst[i] 값을 pop 한다.

이렇게 방문처리/해제, append/pop을 맞춰줘야만
다음 조합이 만들어 진다. 

 

5. n이 N이 될  경우 재귀함수는 멈춰진다.

그리고 재귀함수로 만들어진 리스트들은 문제의 조건으로 계산하고,

최대값을 갱신해준다. 

 

➕ 주의 사항

def dfs(n, rs):
    if n >= N:
        rs_lst.append(rs) # rs 리스트 참조하여 copy 해야함
        return

    for i in range(N):
        if not (visited[i]):
            visited[i] = 1
            rs.append(lst[i])
            dfs(n + 1, rs)
            visited[i] = 0
            rs = [] # 이런경우 다음 그동안 누적했던것들이 초기화 됨

 

만일 문제에서 모든 순열의 조합을 만들라고 할 경우이다. 

위의 코드는 내가 했던 실수들이다. 

현재 문제에서는 rs_lst를 굳이 안만들어고 바로 max를 구하면 된다.

 

첫번째로는, rs =[ ] 이 부분이 잘 못 되었다. 
재귀 함수를 했을 경우, 중간 과정들이 계속 종속적으로 연결되는데
내가 rs = [ ] 로 초기화 해버려 중간 값들을 다 없애버렸다.
rs 전체를 초기화 하지말고, 마지막 부분만 pop 해주면 된다. 

두번째로는  rs_lst에 rs를 append 한 것이다. 
rs는 리스트의 참조(래퍼런스)가 저장되어, rs의 내용이 변경될 때마다,
rs_lst에 저장된 모든 항목도 변경이 된다. 
이를 막기위해 rs[:]를 하든지 rs.copy()로 바꿔주면 된다. 

 

 

📌  문제 코멘트

입력의 모든 리스트의 조합을 만드는게 이 문제의 관건이다.

조합만 만들어지면, 이후 쉽게 반복문으로 문제를 해결 할 수 있다.

 

순열 조합은  itertools 라이브러리의 permutation 함수를 쓰면, 

아주 간단하게 입력의 모든 경우의 리스트를 만들 수 있다. 

 

근데 재귀함수로 코드를 작성하는 것도 의미가 있었기 때문에, 

재귀함수로 문제를 풀어보려고 해보았다.

 

그 과정에서 생각지 못한 실수들이 있었고, 좋은 배움이 되었다. 

---

📚문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1 복사

6
20 1 15 8 4 10

예제 출력 1 복사

62