백준 차이를 최대로 (Python/Go)

문제 링크: www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

N의 범위가 8이하로 작기 때문에 모든 순열을 구해서 풀면 되는 문제입니다.

아래는 파이썬 코드입니다.

import sys
from itertools import permutations
 
 
def get_num(nums):
    tot = 0
    for i in range(1, len(nums)):
        tot += abs(nums[i-1] - nums[i])
    return tot
 
 
n = int(input())
nums = list(map(int, input().split()))
 
answer = -sys.maxsize
for perm in permutations(nums):
    answer = max(answer, get_num(perm))
 
print(answer)

 

아래는 Go코드입니다.

package main
 
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)
 
var n int
var nums []int
var check []int  // 순열 체크용
var answer int = -99999
 
func Dfs(perm []int, lv int) {
    if lv == n {
        tot := GetTotal(perm)
        if answer < tot {
            answer = tot
        }
        return
    }
 
    for i:=0; i<n; i++ {
        if check[i] == 1 {
            continue
        }
        check[i] = 1
        perm = append(perm, nums[i])
        Dfs(perm, lv+1)
        check[i] = 0
        lastIdx := len(perm) - 1
        perm = perm[0:lastIdx]
 
    }
}
 
func GetTotal(nums []int) int {
    tot := 0
    for i:=1; i<n; i++ {
        tot += Abs(nums[i-1]-nums[i])
    }
    return tot
}
 
func Abs(num int) int {
    if num >= 0 {
        return num
    } else {
        return -num
    }
}
func main() {
    fmt.Scanln(&n)
 
    nums = make([]int, n)
    check = make([]int, n)
 
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
 
    for i:=0; i<n; i++ {
        scanner.Scan()
        nums[i], _ = strconv.Atoi(scanner.Text())
    }
 
    var emptySlice []int
    Dfs(emptySlice, 0)
    fmt.Println(answer)
}

기본 내장모듈로 permutation이 없는 것 같아 dfs탐색 방식으로 직접 구현하였습니다.