https://www.acmicpc.net/problem/10819
10819번: 차이를 최대로
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
www.acmicpc.net
<내 코드>
- 백트래킹 연습해야해서 일단 백트래킹으로 구현했다.
- 입력에 같은 숫자가 여러개일수도 있기 때문에 visited 배열을 이용해서 사용한 인덱스를 체크했다.
(이 부분 때문에 틀렸었음)
- 그리고 순서에 따라 값이 달라지기 때문에 dfs에 파라미터 없이 구현했다.
- stack의 길이가 n과 같아지면 반복문을 통해 그 리스트의 값을 계산하고 max_val과 비교해서 업데이트한다.
n = int(input())
nums = list(map(int, input().split()))
max_val = 0 #절댒값의 합이므로 0으로 설정
stack = []
visited = [False]*n
def dfs():
global max_val
if len(stack)==n:
temp = 0
for i in range(n-1):
temp += abs(stack[i]-stack[i+1])
max_val = max(max_val, temp)
return
for i in range(n):
if visited[i] == False:
stack.append(nums[i])
visited[i] = True
dfs()
visited[i] = False
stack.pop()
dfs()
print(max_val)
<permutations 이용 코드>
- 이 문제에선 순서에 따라 값이 달라질수 있기 때문에 순열을 이용해야한다.
from itertools import permutations
n = int(input())
nums = list(map(int, input().split()))
p = list(permutations(nums,n))
max_val = 0
for arr in p:
temp = 0
for i in range(n-1):
temp +=abs(arr[i]- arr[i-1])
max_val = max(temp, max_val)
print(max_val)
'알고리즘 > 백트래킹' 카테고리의 다른 글
[백준-골드5] 1759번 암호 만들기(백트래킹, 파이썬) (0) | 2022.02.07 |
---|---|
[백준-실버2] 6603번 로또(백트래킹, 파이썬) (0) | 2022.02.07 |
[백준-실버2] 15666번 N과 M(12) (백트래킹, 파이썬) (0) | 2022.02.07 |
[백준-실버2] 15665번 N과 M(11) (백트래킹, 파이썬) (0) | 2022.02.07 |
[백준-실버2] 15664번 N과 M(10) (백트래킹, 파이썬) (0) | 2022.02.07 |