<Baekjoon> #16198 DFS, Backtracking_에너지 모으기 c++
구슬이 주어졌을 때 하나씩 제거하다가 마지막 2개가 남았을 때 에너지의 총 합의 최대를 구해야하는 문제다. 예를들어 {a,b,c,d}
의 구슬이 주어졌을 때, 처음 b
를 제거 하고 c
를 제거한 것과 처음 c
를 제거하고 b
를 제거하는 것의 에너지 총 합은 다르기 때문에 에너지 총 합을 구했다가 다시 돌아와서 다른 경우의 에너지 합도 구해야한다. 그러므로 DFS
의 한 방법인 Backtracking
알고리즘으로 구현해야 한다.
dfs
의 종료 조건
제일 앞, 뒤 구슬은 제거할 수 없으므로 마지막 2개가 남아있을 때 에너지 총 합을 구한다.marble
은 처음 구슬의 에너지를 저장한 벡터이고marble
의size
가2
가 되었을 때 max Sum을 구하고 return 한다.if (marble.size() == 2) { maxSum = max(maxSum, sum); return; }
- 구슬을 하나씩 제거
- 구슬은 2개를 남기고 모두 제거해야 하기 때문에
marble.size()-2
만큼for
문을 돌며 제거한다- 제거하는 구슬은 나중에 다시 삽입해야 하기 때문에 임시 변수에 저장하고 합쳐지는 에너지도 따로 저장한다
int tmp = marble[i]; int multi = marble[i - 1] * marble[i + 1];
- 현재 구슬을 제거하고, 에너지의 합을 저장한 뒤 dfs 함수로 다시 넘긴다. 연산이 다 끝나고 돌아왔을 때 다시 원래 있던 위치에 구슬을 넣어준다.
marble.erase(marble.begin() + i); dfs(sum + multi); marble.insert(marble.begin() + i, tmp);
(처음에는 계속 지우고 삽입하고 하는 과정이 너무 복잡할 것 같아서
bool deleted[]
로 두고 지워졌을 때는true
, 아니면false
로 두고 했는데 이게 더 복잡했다)
전체코드
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> marble; int maxSum = 0; void dfs(int sum) { if (marble.size() == 2) { maxSum = max(maxSum, sum); return; } for (int i = 1; i <marble.size()-1; i++) { int tmp = marble[i]; int multi = marble[i - 1] * marble[i + 1]; marble.erase(marble.begin() + i); dfs(sum + multi); marble.insert(marble.begin() + i, tmp); } } int main() { int n; cin >> n; marble = vector<int>(n); for (int i = 0; i < n; i++) cin >> marble[i]; dfs(0); cout << maxSum << endl; return 0; }
Author And Source
이 문제에 관하여(<Baekjoon> #16198 DFS, Backtracking_에너지 모으기 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-16198-DFS-Backtracking에너지-모으기-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)