[백준]10819 차이를 최대로 [Python]

 

위의 문제는 N개의 정수로 이루어진 배열 A의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 구하는 문제입니다.

 

우선 필요한 N개의 정수의 개수를 입력을 받고 N개의 정수를 리스트에 저장합니다.

 

그 다음 최댓값을 저장할 변수하나를 만들고 완전 탐색에서 각 노드에 대해 방문 여부를 저장하는 불리언 값의 배열 visited를 만들어 줍니다.

 

💡visited = [False] * N  ,  visited 배열을 만들 때 입력받은 N개의 개수만큼 만들어 줘야합니다.

 

 

 

이제 완전 탐색의 기본 구조인 함수 부분을 코드로 보면서 설명하겠습니다.

 

위의 함수중에서 밑의 for문을 살펴보면 위에서 만들어준 visited 리스트가 비어있으면 값을 True로 넣어주고 리스트에 해당하는 값을 빈 리스트 li에 append시킨 후 재귀호출을 통해 반복합니다.

 

글로만 보면 이해하기 어려워서 아래의 코드 변화를 눈으로 확인해보면 좀 더 이해하기 편하실 거에요.

 

 

visited 가 True로 바뀌면서 n_list의 첫번째 값인 20을 append합니다. 이런식으로 i 가 5가되면 visited가 전부 True로 바뀌면서 n_list의 모든 값들이 li리스트에 append되게 됩니다.

 

위의 순서대로 양 옆의 값들과의 차이를 합친 total의 값은 50이 됩니다. 아주 많은 경우의 수 중에 하나의 케이스가 돌아가는 모습을 보여드린 것입니다. 이 후에는 pop()을 통해 마지막 값들을 빼가면서 다른 케이스를 만들어서 total의 값을 바꿔서 비교합니다.

 

함수는 재귀식으로 이루어져있고 해당 문제의 값이 양 옆에 위치한 값들의 차를 합친 것을 구하는것이기 때문에

절댓값 함수 abs()를 통해 가장 큰 값을 max()로 추출해 answer에 넣어줍니다.

return으로  if문이 종료가 되면서 answer의 값이 print(answer)로 출력값을 보여줍니다.

 

 

위의 코드는 파이썬으로 구현한 전체 코드입니다.