BOJ
BOJ::16198 에너지 모으기
BOJ Silver 1
BOJ::16198 에너지 모으기
- Link : BOJ::16198
- Level : Silver1
시사점
- backtrack 기본 문제입니다.
- 구슬을 삭제하는 부분을 유의합니다.
키
이해(x)
- 구슬의 갯수와, 각 구슬이 가지고 있는 에너지를 입력받습니다.
- 구슬을 하나씩 뽑아서 제거해가며 모을 수 있는 에너지의 최댓값을 출력합니다.
- 이때, 맨 앞과 맨 뒷 구슬은 뽑을 수 없으며,
- 뽑은 구슬의 왼쪽의 에너지 -1 * 오른쪽의 에너지 +1 만큼이 더해집니다.
설계, 손 코딩(x)
- 손으로 중심이 되는 코드를 구현합니다.
- 구슬이 2개가 되면 게임이 종료됩니다.
- 맨 앞과 맨 뒤는 뽑을 수 없으므로.
- 시간적 여유가 충분해 보이므로, naive하게 벡터의 삭제처리를 진행합니다.
- 물론, erase하는 대신, 새로운 벡터를 하나 만들어서 사용하였습니다.
- 이후 문제에서 원하는 계산을 진행하여 정답을 출력합니다.
시간 복잡도
- O(10!) 정도 예상됩니다.
공간 복잡도
손 코딩 후 문제 리뷰(x)
- 빼먹고 손 코딩 한 것이 있는지 확인합니다.
구현(x)
함수 List
업데이트 되는 변수
- 대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.
실제 구현
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<b;i++)
const int MAXN = 10;
using namespace std;
int n, ans;
int a[MAXN];
void backtrack(int sum, vector<int> LEFT){
if (LEFT.size() == 2){
ans = max(ans, sum);
return;
}
vector<int> NEXT;
rep(i, 1, LEFT.size() - 1){
int psum = LEFT[i - 1] * LEFT[i + 1];
NEXT.clear();
rep(j, 0, i) NEXT.push_back(LEFT[j]);
rep(j, i+1, LEFT.size()) NEXT.push_back(LEFT[j]);
backtrack(sum + psum, NEXT);
}
}
int main(){
//freopen("readme.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
vector<int> LEFT;
cin >> n;
rep(i, 0, n){
cin >> a[i];
LEFT.push_back(a[i]);
}
backtrack(0, LEFT);
cout << ans << '\n';
return 0;
}
구현 후 코드리뷰 + 예제 돌려보기(x)
- 바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.