baekjoon 21757:나누기
21757번 나누기
접근
처음에는 dp(x)를 x가 지금 바라보고 있는 원소 index일 때 x~n-1의 원소 중 정해진 groupSum의 합을 갖는
그룹으로 나누는 가짓수로 정의했다. count도 안넣었던 것이 어짜피 나머지 원소 전체의 합이 있을 때 이를 groupSum으로 나누면 몇 개의 group으로 나뉠지가 정해지니까 였다.
하지만 이 논리가 groupSum이 0인 경우에는 무너지게 되어 count를 넣었다.
그리고 부분합을 이용하여 group의 합을 빠르게 비교했다.
하지만 이렇게 하자 너무 오래걸려 몇개의 서브테스크는 통과하지 못했다.
그 문제로 이 방식이 recursive dp이기 때문이다.(vs iterative dp)
recursive dp는 점화식이 너무 여러갈래로 쪼개지면 시간복잡도가 확 올라간다.
내 실패한 코드에서도 dp(0)을 호출할 때 한 원소씩 추가하면서 살펴보기 때문에 O(n^2)의 시간이 걸린다.
하지만 iterative dp로 풀게 되면 O(n)이면 충분하다.
앞에서부터 부분합을 살펴보면서 groupSum의 3배, 2배, 1배 되는 곳을 세는 것이다.
결과적으로 전체 배열에 칸막이 3개 넣자는 식인데 (앞에서)2번째 칸막이는 자기 앞에 1번째 칸막이의 경우의수에
따라 경우의 수가 결정되고 3배는 앞에 2개를 어떻게 넣는지에 따라 경우의 수가 결정된다. 그런식으로 하기 위해
서로 더해서 넘기는 방식을 쓰면 마지막에 결국 칸막이 3개 넣는 경우의 수가 나오게 된다.
실패한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
#include <array>
#include <fstream>
using namespace std;
long long int partSum = 0;
array<array<long long int, 100000>, 4> cache;
array<long long int, 100001> partialSumCache;
long long int dp(int x, vector<int>& v, int count);
long long int zeroDp(int x, vector<int>& v, int count);
int main(){
ifstream inputFile("inputFile.txt", ios_base::in);
int n; inputFile >> n;
vector<int> v(n);
partialSumCache[0] = 0;
for(int i = 0; i < n; i++) {
inputFile >> v[i];
partSum += (long long int)v[i];
partialSumCache[i+1] = partSum;
}
if(partSum % 4 != 0){
cout << 0;
return 0;
}
partSum /= 4;
fill(cache[0].begin(), cache[0].end(), -1);
if(partSum == 0){
fill(cache[1].begin(), cache[1].end(), -1);
fill(cache[2].begin(), cache[2].end(), -1);
fill(cache[3].begin(), cache[3].end(), -1);
cout << zeroDp(0, v, 0);
// for(int i = 0; i < 3; i++){
// for(int j = 0; j < n; j++){
// cout << cache[i][j] << ' ';
// }
// cout << '\n';
// }
return 0;
}
cout << dp(0, v, 0);
return 0;
}
long long int zeroDp(int x, vector<int>& v, int count){
if(x == v.size()) return 0;
if(count == 3) return 1;
long long int& ret = cache[count][x];
if(ret != -1) return ret;
ret = 0;
for(int i = x; i < v.size(); i++){
if(partialSumCache[i+1] == partSum){
ret += zeroDp(i+1, v, count+1);
}
}
return ret;
}
long long int dp(int x, vector<int>& v, int count){
if(count == 3) return 1;
long long int& ret = cache[0][x];
if(ret != -1) return ret;
ret = 0;
for(int i = x; i < v.size(); i++){
if(partialSumCache[i+1] == partSum * (long long int)(1+count)){
ret += dp(i+1, v, count+1);
}
}
return ret;
}
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <array>
using namespace std;
long long int groupSum = 0;
array<array<long long int, 100000>, 4> cache;
array<long long int, 100000> partialSumCache;
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
groupSum += (long long int)v[i];
partialSumCache[i] = groupSum;
}
if(groupSum % 4 != 0){
cout << 0;
return 0;
}
groupSum /= 4;
for(int i = 0; i < 4; i++){
fill(cache[i].begin(), cache[i].end(), 0);
}
for(int i = 0; i < n-1; i++){
if(i > 0){
cache[1][i] = cache[1][i - 1];
}
if(partialSumCache[i] == groupSum){
cache[1][i]++;
}
}
//1 over
for(int i = 0; i < n-1; i++){
if(i > 0){
cache[2][i] = cache[2][i - 1];
}
if(partialSumCache[i] == groupSum * 2){
cache[2][i] += cache[1][i-1];
}
}
//2 over
for(int i = 0; i < n-1; i++){
if(i > 0){
cache[3][i] = cache[3][i - 1];
}
if(partialSumCache[i] == groupSum * 3){
cache[3][i] += cache[2][i-1];
}
}
//3 over
cout << cache[3][n - 2];
return 0;
}
배운 점
iterative dp를 써서 시간을 단축하자. iterative dp로만 풀리는 경우도 있다.(시간상)