baekjoon 1423:원숭이 키우기
1423번 원숭이 키우기
접근
처음엔 어떻게 dp를 시킬지가 머리에 들어오지 않았다. 항상 dp가 현재 각 캐릭터가 몇명 있는지를 status로 다 들고 있어야할 것 같은데
그럼 너무 경우의 수가 많아져 dp를 쓰는 이유가 없어진다.
그러다가 dp(i) = i일 훈련 시켰을 대의 최댓값으로 정의하고 dp안에다가 status를 배열로 박아버리는 풀이를 시도했다.
어떻게 보면 될 것 같았지만 중대한 문제 2개가 있었다.
j만큼 업글할 때 dp[i-j]로 가는데 이때 dp[i-j]가 최댓값 하나만 가지고 있기 때문에 중간에 같은 최대값을 가지는 여러 status가 있는 경우를 고려하지 못한다.
물론 최종적으로 답을 낼 땐 그게 문제 없는데 중간에는 최대값을 둘다 가지지만 하나가 나중에 더 좋은 status일 수도 있다.
그리고 dp에 status를 배열로 박아버리는 것도 좀 아닌것 같아서 다른 방법을 고안해야했다.
그래서 2번째로 시도한 코드는 역시 status를 다 필요하지 않고 일부만으로 dp를 할 수 있었다.
앞에서부터 업그레이드 시키도록 순서를 정해주면 되었다. 그럼 dp(업그레이드 대상 레벨, 직전레벨에서 업그레이드 되서 온 캐릭터 수, 남은 일 수)
이렇게 dp를 만들 수 있다.
실패한 코드
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
//1423 failure
#include <iostream>
//dp[0] 0일 훈련 시켰을 때 최댓값
//for i in 1~D
// dp[i] = dp[i-1]
// for j in 0~i-1 얼마나업글
// for k in 1~ N 어떤거 업글?
// new_map = {1:e1, ... k:ek-1, k+j:ej+1, ...}
// where {1:e1, ... n:en} <- dp[i-j]
// if pow(new_map) > pow(dp[i-1])
// dp[i] = new_map
#include <vector>
#include <array>
using namespace std;
struct dp{
array<int, 50> charNum;
long long int power;
};
long long int calPower(array<int, 50>& _charNum);
array<dp, 51> cache;
array<int, 50> power;
array<int, 50> charNum;
int main(){
int n; cin >> n;
for(int i = 0; i < n; i++){
cin >> charNum[i];
}
for(int i = 0; i < n; i++){
cin >> power[i];
}
int d; cin >> d;
cache[0] = {charNum, calPower(charNum)};
for(int i = 1; i <= d; i++){
cache[i] = cache[i-1];
for(int j = 0; j <= i; j++){
for(int k = 1; k <= n; k++){
array<int, 50> newCharNum = cache[i-j].charNum;
if(newCharNum[k-1] == 0) continue;
newCharNum[k-1]--;
newCharNum[k+j-1]++;
if(calPower(newCharNum) > cache[i-1].power){
cache[i] = {newCharNum, calPower(newCharNum)};
}
}
}
}
cout << cache[d].power;
return 0;
}
long long int calPower(array<int, 50>& _charNum){
long long int ret = 0;
for(int i = 0; i < _charNum.size(); i++){
ret += (long long int)_charNum[i] * (long long int)power[i];
}
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <array>
#include <iostream>
#include <vector>
#include <cstring>
// dp(int i, int upgraded)
using namespace std;
array<array<array<long long int, 101>, 101>, 51> cache;
long long int dp(int i, int upgraded, int remainDays, vector<int> &charCount,
vector<int> &power);
int n;
int main() {
cin >> n;
vector<int> charCount(n+1);
vector<int> power(n+1);
for (int i = 1; i < n+1; i++) {
cin >> charCount[i];
}
for (int i = 1; i < n+1; i++) {
cin >> power[i];
}
int d;
cin >> d;
// for(int i = 0; i < 51; i++){
// for(int j = 0; j < 101; j++){
// fill(cache[i][j].begin(), cache[i][j].end(), -1);
// }
// }
for (auto &i: cache) { //다차원 array 쉽게 채우는 법
for (auto &j: i) {
j.fill(-1);
}
}
// for(int i = 0; i < 11; i++){
// for(int j = 0; j < 11; j++){
// for(int k = 0; k < 6; k++){
// cout << cache[i][j][k] << " ";
// }
// cout << "\n";
// }
// }
// for(auto i : charCount){
// cout << i << " ";
// }
cout << dp(1, 0, d, charCount, power) << "\n";
// for(int i = 0; i < 11; i++){
// for(int j = 0; j < 11; j++){
// for(int k = 0; k < 6; k++){
// cout << cache[i][j][k] << " ";
// }
// cout << "\n";
// }
// }
return 0;
}
long long int dp(int i, int upgraded, int remainDays, vector<int> &charCount,
vector<int> &power) {
if (i == n) {
return (long long int)power[i] * (long long int)(charCount[i] + upgraded);
}
long long int &ret = cache[i][upgraded][remainDays];
if (ret != -1)
return ret;
int maxUpgrade = min(charCount[i] + upgraded, remainDays);
for (int j = 0; j <= maxUpgrade; j++) {
long long int nextResult = dp(i + 1, j, remainDays - j, charCount, power);
long long int diff =
(long long int)power[i] * (long long int)(charCount[i] + upgraded - j);
ret = max(ret, nextResult + diff);
}
return ret;
}
배운 점
관점을 바꿔서 dp하기 어려워 보였던 것도 결국은 dp할 수 있도록 바꿔내는게 핵심이다.
그렇지만 이 문제를 풀고나서 나는 처음엔 앞에서부터 작은 level부터 더해나가는게 iterative dp인줄 알았는데
살펴보면 recursive dp이다.
ac21757: 나누기 문제에서 실패했던 것처럼 for문을 쓰고 있는데 왜 이 문제에서는 시간 초과가 나지 않았을까를 생각해보면
dp의 시간복잡도는 대부분 dp가 채우는 배열의 크기 \(\times\) 각 dp가 걸리는 시간 으로 대강 예상 가능하다.
이 문제는 배열의 크기는 \(100\times 100\times 50\)정도이고 각 dp에서 for문이 가장 시간 오래걸리니까 for문 생각해보면
최대 100번 돌 수 있다. 따라서 \(100\times 100\times 50\times 100 = 50000000\)으로 1억이 넘지 않아서 최대 1초보다 덜 걸린다.
하지만 ac21757의 경우 배열의 크기가 400000이고 각 dp의 for문도 최대 100000번 돌 수 있어서 400억이 되어버려서 그랬던 것이다.
따라서 recursive dp에서 for문 쓰는거도 어느정도 충분히 가능한 풀이다. 즉, 시간 복잡도 계산해보고 쓰라는 것이다.