[백준] 10819 차이를 최대로

1. 문제

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

2. 풀이

 

백트래킹도 좀 감이 오는거같다!! 후 코테 이제 드루와 (사실 들어오지 마세요ㅠ

 

문제는 연속된 숫자끼리의 차이 절댓값을 max로 만드는거고, 우선 백트래킹으로 푸는거에 중점을 뒀다.

 

1) total_max라는 전역변수 만들어주고, 어디서 처음 계산을 시작할지 한번씩 돌려준다.

2) 백트래킹 함수 내부: 다돌았을때 멈춘다 (return). total이 크면 바꿔준다.
visited는 index 저장 공간이고, 제일 최근 값과 다음 값의 차이가 max인 경우를 다음 방문으로 설정한다.
그리고 또 다시 재귀로 돌리기~

 

## code ##

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

def bt(visited: list, total: int):
    global total_max
    # print(visited, total)
    if len(visited) >= len(nums):
        if total > total_max:
            total_max = total
        return

    max_val, max_idx = 0, 0

    for j in range(n):
        if j not in visited:
            if max_val < abs(nums[visited[-1]] - nums[j]):
                max_val = abs(nums[visited[-1]] - nums[j])
                max_idx = j
    visited.append(max_idx)
    bt(visited, total + max_val)

total_max = 0
for i in range(n):
    bt([i], 0)
print(total_max)

 

 

+ 그거 아시나요 ???

global / nonlocal의 차이를 ,,,

* global : main의 변수 (global 변수) 를 함수 내부 변수로 공유하도록 하는 선언
* nonlocal : 큰 함수 내부 안에 다른 함수가 있다면, 큰 함수의 변수를 내부 함수와 공유하도록 선언

 

자 그래서 재밌게도 코드를 전체 짜는 백준은 보통 global을 자주 활용하고

제출하는 코드가 함수고 우리가 그 내부를 짜는 프로그래머스에는 보통 nonlocal을 쓴다,,

ㅋㅋㅋ ㅋ