문제 링크 : 백준 2262번
[문제 접근]
그리디 알고리즘을 이용해서 풀었다.
랭크가 낮은 선수가 계속 살아남을 수록 전체 합이 커지므로 랭크가 낮은 선수를 우선으로 경기를 시켜야한다.(다른 의미로 랭크가 높은 선수는 가장 마지막에 경기하는 것이 좋다.)
따라서 전체 배열 중에 랭크가 가장 낮은 선수를 선택하고 그 선수 주변에 있는 선수 중에 랭크가 더 낮은 선수와 경기한다.
[소스 코드]
package main
import (
"bufio"
"fmt"
"os"
)
var (
r = bufio.NewReader(os.Stdin)
w = bufio.NewWriter(os.Stdout)
n int
arr []int
)
func Abs(num int) int {
if num < 0 {
return -num
}
return num
}
func max() int {
num, idx := 0, 0
for i := 0; i < len(arr); i++ {
if num < arr[i] {
num, idx = arr[i], i
}
}
return idx
}
func main() {
defer w.Flush()
fmt.Fscan(r, &n)
for i := 0; i < n; i++ {
var a int
fmt.Fscan(r, &a)
arr = append(arr, a)
}
ans := 0
for i := 0; i < n-1; i++ {
idx := max()
if idx == 0 {
ans += Abs(arr[idx] - arr[idx+1])
arr = arr[1:]
} else if idx == len(arr)-1 {
ans += Abs(arr[idx] - arr[idx-1])
arr = arr[:len(arr)-1]
} else {
var num int
if arr[idx-1] > arr[idx+1] {
num = arr[idx-1]
} else {
num = arr[idx+1]
}
ans += Abs(arr[idx] - num)
arr = append(arr[:idx], arr[idx+1:]...)
}
}
fmt.Fprintln(w, ans)
}