25378 조약돌

Link

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

Detail

처음에는 탑다운방식으로 해결하려고 했으나, 해당 방식이 메모리 부하를 일으켜 Tabulation으로 그 방법을 수정하였다.

핵심 아이디어는 다음과 같다.

• 모든 조약돌은 최대 N회만에 전부 회수가 가능하다.
• 두 영역의 조약돌을 회수하여 동시에 0으로 만들 수 있을경우, 그 횟수를 줄일 수 있다.

따라서 해답 로직은 다음과 같다.

• i번째 돌을 회수할 때, i - 1번째 돌이 존재할 수 있는 모든 경우의 수를 연산한다.
• 연산해서 완전히 0으로 만들 수 있을 경우, 해당 경우를 채택한다.

Code

#include <iostream>  
#include <vector>  
using namespace std;  
  
int solve(const vector<int>& stones) {  
    vector<vector<int>> remains(stones.size());  
    for (int i = 0; i < stones.size(); i++){  
       remains[i].push_back(stones[i]);  
    }  
  
    int answer = (int)stones.size();  
    for (int i = 1; i < stones.size(); i++){  
       for (auto st : remains[i - 1]) {  
          if (stones[i] > st) {  
             remains[i].push_back(stones[i] - st);  
          }  
  
          else if (stones[i] == st) {  
             remains[i].clear();  
             answer--;  
             break;  
          }  
       }  
    }  
  
    return answer;  
}  
  
int main(){  
    int n;  
    cin >> n;  
    vector<int> stones(n);  
    for (int i = 0; i < n; i++){  
       cin >> stones[i];  
    }  
  
    cout << solve(stones) << "\n";  
    return 0;  
}