BOJ 16198

16 Apr 2020 • ProblemSolving

에너지 모으기

문제출처

문제 해석

  • 다음 조건을 반복해서 모을 수 있는 에너지 양의 최댓값을 구하는 문제입니다.
    1. 에너지 구슬 x를 하나 고릅니다. 단, 첫번째와 마지막은 고를 수 없습니다.
    2. x번째 에너지 구슬을 제거하고, WX-1xWX+1의 에너지를 모을 수 있습니다.
    3. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지 다시 번호를 매깁니다.

설계(5)

  • 범위가 적어 완전탐색으로 풀이가 가능할 것으로 보입니다.
  • 에너지 사용 여부를 visited배열로 판별합니다.
  • idx변수를 이용하여 사용한 에너지를 제외하고 몇번째 에너지 구슬인지 체크해줍니다.
  • i번째 구슬을 고른 후, 반복문을 이용하여 idx-1, idx+1번째 구슬을 찾은 후 곱하고 더해줍니다.

구현(10)

코드
#include <iostream>
using namespace std;

#define MAXN 10

int W[MAXN];
bool visited[MAXN];
int N,ans;
void backtrack(int len, int sum){
    if (len <=2 ) {
        if (ans < sum) ans = sum;
        return;
    }
    int idx = 0;
    for (int i = 0; i<N; i++){
        if (visited[i]) continue;
        if (idx>0 && idx<len-1){
            visited[i] = true;
            int j1 = i;
            int j2 = i;
            while (--j1>=0&&visited[j1]);
            while (++j2<N&&visited[j2]);
            backtrack(len-1,sum+W[j1]*W[j2]);
            visited[i] = false;
        }
        idx++;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i =0 ;i<N; i++){
        cin >> W[i];
    }
    backtrack(N,0);
    cout << ans <<"\n";
    return 0;
}
디버깅
제출결과
  • 4 ms

마무리

  • 단순 백트래킹 문제였습니다. 사용한 에너지 구슬을 제외하고 인덱스를 카운트 해주는 방식이 키포인트였습니다.
 BOJ

Related Posts