[BOJ] 에너지모으기

문제

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)

풀이

16198

맞았습니다!!

1988

0

C++14 / 수정

857

37초 전

1. 재귀 + 브루트포스

 

2. 재귀를 돌면서 계산을 하고 백트래킹을 한다. 

에너지에서 빠져야 하는 x구슬을 방문 처리하여 다음에 중복 계산되지 않도록 한다. 

 

3. visited된 구슬들은 인덱스에 포함되지 않아야 하기 때문에 왼편광 오른편에 있는 방문하지 않는 구슬을 찾아줘야 한다. 

left = x-1 , right = x+1 로 두고 while로 끝까지 탐색해준다.

 

4. dfs에는 파라미터로 고른 구슬의 수와 (n-2까지 구해준다) 모은 에너지의 양이 들어간다. 

 

5. 종료조건 

cnt == n-2라면 최대값을 비교한다. 

 

---

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, ans, energy[10];
bool visited[10];
 
typedef long long ll;
 
void dfs(int cnt, int sum) {
    if (cnt == n-2) {
        ans = max(sum, ans);
        return;
    }
 
    for (int i = 1; i < n-1; i++) {
        if (!visited[i]) {
            int left = i-1, right = i+1;
 
            while(visited[left] && left >= 0) 
                left--;
            
            while(visited[right] && right < n) 
                right++;
            
            visited[i] = true;
            dfs(cnt+1, sum + energy[left] * energy[right]);
            visited[i] = false;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) 
    {
        cin >> energy[i];
    }
 
    dfs(0,0);
 
    cout << ans << '\n';
    return 0;
}