16198 에너지 모으기

16198 에너지 모으기 / c++ / Silver1 / 27분

문제 및 코드

풀이 과정

완전 탐색 / 백트래킹

1. N개의 구슬이 들어간 배열에서, i번째 구슬의 무게를 W_i라고 할때, i번째 구슬을 제거하는 경우 [W_i-1 * W_i+1]의 에너지를 얻게 된다. 이 때 얻을 수 있는 에너지의 최대값을 출력하는 문제. (단, 맨 앞과 맨 뒤의 구슬은 제거 불가능)
2. 이 문제를 해석해보면, N은 최대 10 이므로, 10개 중 맨 앞뒤 구슬을 제외한 나머지 8개의 순열을 구하는 문제이다. ₁₀P₈
3. 중복을 허용하지 않기 때문에 이는 10! - (10-8)! 이고, 값은 1,814,400로 충분히 1초 안에 연산해 낼 수 있는 문제이다.
4. 따라서 완전 탐색을 진행하고, 이전 값을 기억해 다음 계산에 활용하는 백트래킹으로 효율을 높인다.
5. 시작값이 0인 상태에서 백트래킹을 시작.
6. 만약 현재 구슬의 개수가 2개 (맨앞맨뒤만 남음)이면, 현재까지의 값이 Answer보다 큰 경우 갱신 후 종료, 아닐 경우 그냥 종료
7. 현재 구슬의 개수가 3개 이상이라면, 맨앞과 맨뒤를 제외한 구슬을 순회하며 아래 로직 수행
8. i번째 구슬을 제거 후 1번의 공식에 따라 에너지를 더해서 다시 백트래킹 진행
9. 8번의 백트래킹 종료 후 다시 i번째에 제거 했던 구슬을 삽입
10. 모든 백트래킹이 종료된 후 Answer를 출력
11. 해결

회고

1. 처음엔 그리디로 접근했다. 한 번 순회하면 현재 기준 가장 높은 에너지를 뽑아낼 수 있는 구슬을 제거하는 식 (단 기대치가 같으면 무게가 가벼운 구슬을 제거)
2. 하지만 이는 그리디의 단점과 같이, 당장에는 최적의 값이지만 축적됐을 때는 항상 최적의 값이 되진 않는다.
3. 그래서 다시 생각해보니 N이 10이므로 충분히 완전 탐색을 할 수 있었고, 백트래킹으로 접근해서 해결할 수 있었다.