- 링크
https://leetcode.com/problems/minimum-sum-of-values-by-dividing-array/description/
- 내가 푼 방법
풀이를 봤다. 너무 어려운 문제였다. 하지만, 풀이는 초반에 생각했던 방식과 비슷했다. 물론 엄청난 사실이 숨어있지만 말이다.
공식적인 Solution으로 제공하는 것은 세그먼트 트리, 슬라이딩 윈도우, 바이너리 서치 등을 활용하는 것 같다. 하지만, 다른 이가 올린 풀이가 정말 깔끔해서 이를 따랐다.
그냥 일반적인 dp 방식이다. 딱 특정 idx를 기준으로 split하고 나면 And를 초기화해 주면 되는 것이다. 즉, And 연산을 다시 처음부터 시작하는 것이다.
아주 간단하지만, 여기에는 숨겨진 사실이 있다. 이 점만 짚어보고 넘어갈 생각이다.
- 왜 (1 << 17) - 1을 초기 And 값으로 넣는 것일까?
처음에 계속 헤맸다. 바보 같이, 아 주어진 andValues의 최댓값이 1e5니까 그냥 1e5+1을 넣어야지~ 한 게 화근이었다.
(1<<17)-1을 한 이유는 andValues의 최댓값을 넘기며 모든 비트가 1이어서 And 연산을 진행할 때 And 값의 영향을 받지 않게끔 하는 것이다.
- 왜? 이게 시간초과가 안될까?
그냥 촉으로만 보면 시간초과가 무조건 될 코드이다.
이유는, 이미 dp의 사이즈만 해도 n * m인데, 연산했던 And의 결과물들도 계속해서 들어가니 사이즈는 말도 안 되게 커진다.
하지만, 잘 생각해 보면 그렇지 않다. And 연산의 특징은 수가 계속 작아진다는 특징이 존재한다. 그리고 0이던 비트를 1로 만들 수 없다. 가능한 것은 1이던 비트를 0으로 끌어내리는 방법밖에 없다. 즉 값이 감소할 때는 1이던 비트 중 1개를 0으로 끌어내리는 것이고, 이것은 최대 max_element의 1비트의 개수만큼 가능하다.
그러므로 log(max_element)만큼만 시간복잡도가 곱해지는 것이다.
정리하면, dp[i][j].size()는 최대 log(max_element)이다.
위 두 가지 개념을 확실히 인지하고 있다면, 이 문제는 정말 쉽게 풀 수 있다. 하지만 위 시간 복잡도를 계산하기가 쉽지만은 않다. 계속된 연습을 통해서 익혀야겠다.
- 시간 복잡도
O(n m log(max_element));
- Correct Code
class Solution {
public:
vector<int>nums;
vector<int>andValues;
vector<vector<unordered_map<int,int>>>dp;
int n,m;
int dfs(int idx,int aIdx,int And){
if(idx==n){
if(aIdx==m){
return 0;
}
return 1e8;
}
if(aIdx==m){
return 1e8;
}
if(dp[aIdx][idx][And]){
return dp[aIdx][idx][And];
}
int inclu=1e8;
if((And&nums[idx])==andValues[aIdx]){
inclu=dfs(idx+1,aIdx+1,(1<<17)-1)+nums[idx];
}
int exclu=dfs(idx+1,aIdx,And&nums[idx]);
return dp[aIdx][idx][And]=min(inclu,exclu);
}
int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
this->nums=nums;
this->andValues=andValues;
this->n=nums.size();this->m=andValues.size();
dp.resize(m,vector<unordered_map<int,int>>(n));
int result=dfs(0,0,(1<<17)-1);
return result==1e8?-1:result;
}
};