[DFS] 16198번 에너지 모으기

16198번 에너지 모으기

 

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

 

문제

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

1. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
2. x번째 에너지 구슬을 제거한다.
3. Wx-1 × Wx+1의 에너지를 모을 수 있다.
4. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.

N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.

둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

 

출력

첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.

 

예제 입력

4
1 2 3 4

5
100 2 1 3 100

7
2 2 7 6 90 5 9

10
1 1 1 1 1 1 1 1 1 1

 

예제 출력

12

10400

1818

8

 

해결방법

DFS + 백트래킹을 통해 모든 경우를 다해보는 부르트 포스 문제이다

시간복잡도 : O(2^8)

 

 

문제에서 주어진 조건은 아래와 같다

1. 양쪽 끝 에너지 구슬은 뺄 수 없다
2. 하나를 뺏으면 왼쪽으로 당겨야 한다

 

1번 조건이야 for문으로 간단히 해결되지만 2번 조건이 문제였다

백트래킹을 수행해야 하는데 왼쪽으로 배열을 당길 수 없었기 때문이다

계속 생각을 해보다가 한가지 솔루션이 떠올랐다

 

1. 구슬을 뺏으면 그 노드는 false로 설정한다

2. 양쪽 끝 노드는 뺄 수 없기 때문에 왼쪽과 오른쪽으로 계속 이동하면서 true인 노드를 찾는다

3. true인 노드의 값을 반환한다

 

아래와 같이 왼쪽과 오른쪽의 노드를 구하는 코드를 작성하였다

int getLeft(int ind){
    int l = ind;
    while(true) {
        l--;
        if(!visited[l]){
            break;
        }
    }
    return map[l];
}

int getRight(int ind){
    int r = ind;
    while(true) {
        r++;
        if(!visited[r]){
            break;
        }
    }
    return map[r];
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 11
#define INF 987654321
using namespace std;

int n,ans;

int map[MAX];
bool visited[MAX];

int getLeft(int ind){
    int l = ind;
    while(true) {
        l--;
        if(!visited[l]){
            break;
        }
    }
    return map[l];
}

int getRight(int ind){
    int r = ind;
    while(true) {
        r++;
        if(!visited[r]){
            break;
        }
    }
    return map[r];
}

void dfs(int cnt,int energy){
    // 정답을 찾은 경우
    if(cnt == n-2){
        ans = max(ans,energy);
        return;
    }
    
    // DFS 탐색
    for(int i=1; i<n-1; i++){
        if(!visited[i]){
            visited[i] = true;
            
            // 에너지 계산
            int l = getLeft(i);
            int r = getRight(i);
            dfs(cnt+1, energy+(l*r));
            
            visited[i] = false;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> map[i];
    }
    
    memset(visited, false, sizeof(visited));
    ans = 0;
    dfs(0,0);
    cout << ans << "\n";
    return 0;
}