[BOJ/백준] 16198 에너지 모으기

● [문제번호 16198] 에너지 모으기

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

16198번: 에너지 모으기

 

 

● 알아야 할 것

: DFS

: 재귀

: 브루트 포스 (Brute Force)

 

 

● 풀이 과정

: 모든 경우의 수를 확인해서 에너지 양의 최댓값을 구하면 된다.

 

: 재귀를 이용한 DFS를 구현하여 각 단계에서 선택한 에너지 구슬을 고려하면 된다.

1. 에너지 구슬 체크인
2. 선택한 에너지 구슬의 양 옆 에너지 구슬의 무게 구하기
3. energy에 추가
4. 재귀
5. energy에서 빼기
6. 에너지 구슬 체크아웃

 

 

● 주의 할 것

: NULL

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// visited : 각 에너지 구슬의 방문기록
// weight : 에너지 구슬의 무게 저장
// sol : 에너지 양의 최댓값 저장
bool visited[1001];
int weight[1001];
int N, sol;

// (center기준) 왼쪽 visited값이 false인 index 반환
int before(int center)
{
    int i = center - 1;
    
    for(; i >= 0; i--)
        if(!visited[i])
            break;
    
    return i;
}

// (center기준) 오른쪽 visited값이 false인 index 반환
int after(int center)
{
    int i = center + 1;
    
    for(; i < N; i++)
        if(!visited[i])
            break;
    
    return i;
}

// cnt : visited값이 true인 갯수
// energy : 현재 깊이까지 구한 energy값
void dfs(int cnt, int energy)
{
    // N-1 개 이상 선택한 경우
    if(cnt >= N - 1)
        return ;
    
    // 에너지 양의 최댓값 UPDATE
    if(sol < energy)
        sol = energy;
    
    // 에너지 구슬 양끝을 제외하고 반복
    for(int i = 1; i < N - 1; i++)
    {
        // 방문하지 않은 에너지 구슬 선택
        if(!visited[i])
        {
            // 1. 에너지 구슬 체크인
            // 2. 선택한 에너지 구슬의 양 옆 에너지 구슬의 무게 구하기
            // 3. energy에 추가
            // 4. 재귀
            // 5. energy에서 빼기
            // 6. 에너지 구슬 체크아웃
            visited[i] = true;
            int temp = weight[before(i)] * weight[after(i)];
            energy += temp;
            dfs(cnt + 1, energy);
            energy -= temp;
            visited[i] = false;
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    for(int n = 0; n < N; n++)
        cin >> weight[n];
    
    // 재귀 시작
    // 0개선택, 여태 모은 에너지는 0
    dfs(0, 0);
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [531 - 브루트 포스 - 재귀 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	6603	로또	https://pirateturtle.tistory.com/301
2	1182	부분수열의 합	https://pirateturtle.tistory.com/302
3	14225	부분수열의 합	https://pirateturtle.tistory.com/303
4	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/304
5	15658	연산자 끼워넣기 (2)	https://pirateturtle.tistory.com/305
6	14500	테트로미노	https://pirateturtle.tistory.com/306
7	16197	두 동전	https://pirateturtle.tistory.com/307
8	16198	에너지 모으기	https://pirateturtle.tistory.com/308
9	9663	N-Queen	https://pirateturtle.tistory.com/309
10	2580	스도쿠	https://pirateturtle.tistory.com/310
11	4574	스도미노쿠	https://pirateturtle.tistory.com/311
12	1987	알파벳	https://pirateturtle.tistory.com/312