[Swift][BruteForce] 백준 16198번 (에너지 모으기)

요구능력 : 백트래킹

 

코드설명 : 

 

문제에서의 핵심

1. 구슬 하나를 고른다.(단, 첫번째구슬과 마지막구슬을 고르면 안됨)

2. x번째 에너지구슬 제거(고른 구슬을 제거해야한다.)

3. Wx-1 * Wx+1 의 에너지모음( Wx-1 * Wx+1의 모든경우를 합해야한다.)

4. N을 1감소시킴. 구슬 1~N까지 다시 번호매김.

 

예제

4

1 2 3 4 가있다.

2를 고르면  Wx-1 * Wx+1이 1 *3이 된다.

그리고 첫번째와 마지막은 못고르니까 3을 고른다.

3을 고르면  Wx-1 * Wx+1이 1 * 4가 된다.

그럼 에너지는 총 8이 모인다.

 

맨 처음에 3을 고른다.

그럼  Wx-1 * Wx+1이 2*4가 된다.

그 다음 2를 고르면  Wx-1 * Wx+1이 1 * 4가 되서 12가 나온다.

 

이렇게 어느 구슬을 고르는지에 따라 결과값이 달라진다.

그럼 구슬이 나올 수 있는 모든 경우의 수를 다 따져봐야 할것이다.

그래서 백트래킹을 사용한다.

 

맨 처음구슬과 맨 마지막구슬만 남을경우의 에너지의 합이므로 결국 배열이 2개가되면 에너지값을 도출해야한다.

if arr.count == 2{
        result = max(result, sum)
        return
    }

 

맨 처음과 맨 마지막의 에너지구슬을 계산하면 안되니까 1..<n-1로 범위를 잡는다.

그리고 문제에서 제시한대로 에너지의 곱을 구해서 sum에 누적해준다.

그 후로 해당하는 인덱스에 대한 값을 제거하고 pop변수에 저장해준다.

백트래킹을 돌면서 백트래킹이 리턴될때마다 원래자리에 값을 돌려놓는다.

그리고 당연히 누적된값도 빼준다.

for i in 1..<n - 1{
        if i + 1 >= arr.count{
            continue
        }
        sum += arr[i - 1] * arr[i + 1]
        let pop = arr.remove(at: i)
        dfs()
        arr.insert(pop, at: i)
        sum -= (arr[i - 1] * arr[i + 1])

    }

 

 

나는 풀다가 아래 예제에서  indexOutOfRange가 걸려서 디버깅해보니까

처음에  2 -> 7 -> 6 -> 90 -> 5 까지 백트래킹으로 한바퀴 돌고나서

arr배열에 [2, 5, 9]가 들어있는데 i가 2인 상태라서 오류가 났다.

즉, 내가 원하던건 2 -> 7 -> 6 -> 90 -> 5의 다음 백트래킹인 2 -> 7 -> 6 -> 5 -> 90 로 돌기를 바랬는데 이렇게 돌려면

[2, 5,  90, 9]이 들어있어야 된다.

그래서 i + 1 >= arr.count 조건문을 넣어주었다.

7
2 2 7 6 90 5 9

 

 

후기 : 백트래킹에 대해 알고있는지를 묻는문제..? 같았다.

let n = Int(String(readLine()!))!
var result = 0
var sum = 0
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}

func dfs(){

    if arr.count == 2{
        result = max(result, sum)
        return
    }

    for i in 1..<n - 1{
        if i + 1 >= arr.count{
            continue
        }
        sum += arr[i - 1] * arr[i + 1]
        let pop = arr.remove(at: i)
        dfs()
        arr.insert(pop, at: i)
        sum -= (arr[i - 1] * arr[i + 1])

    }
}

dfs()
print(result)