[백준] 16198 | 에너지 모으기 | C++

풀이의 핵심은 이렇다.

0. 입력받은 에너지값들(배열 inp)을 마음껏 조작할 수 있도록
객체 하나를 복사생성해둔다(배열 cpy).

1. DFS는 처리해야 할 구슬의 순서(배열 ord)를 작성한다.

2. 순서구성이 완료되면:
    계산할 에너지합 변수 선언(tmp = 0)
    구슬처리(cpy조작) 위한 순서탐색(for ord):
        해당순서(ord[i])의 에너지값을 사용했단 의미에서 0을 대입(cpy[ord[i]]=0)
        해당순서의 이전순서(ord[i]-1)를 l, 다음순서(ord[i]+1)를 r로 선언
        사용되지 않은(0이 아닌) 구슬을 찾기 위해 l, r 세팅
        세팅완료된 l, r을 이용하여 tmp에 에너지 모은다.
    모아둔 tmp가 res보다 크다면 res 갱신

3. 최댓값 res를 출력

 

0.

구슬을 사용하면 그 구슬을 '0'으로 조작하기 위해서

배열 inp와 똑같이 생성된 배열 cpy을 복사해둔다.

memcpy(cpy, inp, sizeof cpy);

 

1.

DFS의 본체는 처리할 구슬의 순서를 작성하는 역할을 한다.

처리순서는 배열 ord에 작성하도록 할 것이다.

두번째 구슬(i=1)부터 마지막의 이전 구슬(i=n-2)까지 처리하도록 한다.

void DFS(int L) {
    ...
    
    for(int i=1; i<=n-2; i++) {
    	...
    	ord[L]=i;
    	...
    }
}

 

2.

순서구성이 완료되면(기저조건),

먼저 모아둘 에너지합 변수 tmp를 선언한다.

int tmp=0;

 

순서가 담긴 ord를 차례로 탐색한다.

for(int i=0; i<n-2; i++) {
    ...
}

 

해당순서(ord[i])의 구슬을 사용했단 의미에서 '0'으로 초기화한다.

cpy[ord[i]]=0;

 

해당순서의 이전순서(ord[i]-1)을 l, 다음순서(ord[i]+1)를 r로 선언한다.

int l=ord[i]-1, r=ord[i]+1;

 

l과 r 위치에 있는 구슬은 이미 사용됐을 수도 있다.

cpy[l] 또는 cpy[r]이 이미 0일수 있다는 뜻이다.

사용되지 않은 구슬을 찾아 l과 r을 세팅한다.

while(cpy[l]==0) l--;
while(cpy[r]==0) r++;

 

l과 r을 찾으면 tmp에 에너지를 모아둔다.

tmp=cpy[l]*cpy[r];

 

출력값(res)을 갱신해준다.

res=max(res, tmp);

 

다음 DFS에서도 정확히 에너지를 계산할 수 있도록

가공된 cpy를 다시 원본인 inp에 맞춘다.

memcpy(cpy, inp, sizeof cpy);

 

3.

최댓값 res를 출력한다.

cout<<res<<"\n";

 

정답 소스코드

#include<bits/stdc++.h>
using namespace std;

int n, res=0;
int inp[14], cpy[14], ord[14];
bool chk[14];

void input() {
    cin>>n;
    for(int i=0; i<n; i++) cin>>inp[i];
    memcpy(cpy, inp, sizeof cpy);
}

void DFS(int L) {
    if(L==n-2) {
        int tmp=0;
        for(int i=0; i<n-2; i++) {
            cpy[ord[i]]=0;
            int l=ord[i]-1, r=ord[i]+1;
            while(cpy[l]==0) l--;
            while(cpy[r]==0) r++;
            tmp+=cpy[l]*cpy[r];
        }
        res=max(res, tmp);
        memcpy(cpy, inp, sizeof cpy);
        return;
    }

    for(int i=1; i<=n-2; i++) {
        if(!chk[i]) {
            chk[i]=true;
            ord[L]=i;
            DFS(L+1);
            chk[i]=false;
        }
    }
}

void output() {
    cout<<res<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    input();
    DFS(0);
    output();
    return 0;
}