w## 📝 문제 정보
문제#
JOI 군은 점심으로 중화요리집에서 샤오롱바오를 먹기로 했다. 샤오롱바오는 속재료와 뜨거운 국물을 밀가루 피로 싼 요리로, 먹을 때 국물이 주위로 튀는 것으로 알려져 있다.
JOI 군이 주문한 샤오롱바오 세트는 속재료나 국물이 다른 N개의 샤오롱바오로 이루어져 있다. N개의 샤오롱바오는 등간격으로 일렬로 놓여 있으며, 순서대로 1부터 N까지 번호가 매겨져 있다. i번째 샤오롱바오와 j번째 샤오롱바오 사이의 거리는 절댓값 |i - j|이다.
JOI 군은 샤오롱바오를 어떤 순서로 먹어나간다. 처음에 모든 샤오롱바오의 맛있음은 0이다. i번째 샤오롱바오를 먹으면, 주위로 그 국물이 튀어서, 아직 먹지 않은 샤오롱바오 중에서 샤오롱바오 i로부터의 거리가 $D_i$ 이하인 샤오롱바오에 국물이 묻는다. 국물이 묻은 샤오롱바오는 맛있음이 $A_i$만큼 증가한다. 즉, i번째 샤오롱바오를 먹었을 때, j번째 샤오롱바오 ($1 \leq j \leq N$ 이고 $i - D_i \leq j \leq i + D_i$)가 아직 먹지 않고 남아있다면, j번째 샤오롱바오의 맛있음이 $A_i$만큼 증가한다.
JOI 군은 먹는 순서를 잘 정해서, 먹는 샤오롱바오의 맛있음의 합계를 최대화하고 싶다. 가장 좋은 순서로 먹었을 때, JOI 군이 먹는 샤오롱바오의 맛있음의 합계를 구하는 프로그램을 작성하시오.
입력#
입력 파일은 3행으로 이루어진다.
- 1행에는 정수 N ($1 \leq N \leq 100$)이 주어진다.
- 2행에는 N개의 정수 $D_1, D_2, \ldots, D_N$ ($0 \leq D_i \leq 7$)이 공백으로 구분되어 주어진다.
- 3행에는 N개의 정수 $A_1, A_2, \ldots, A_N$ ($0 \leq A_i \leq 1000$)이 공백으로 구분되어 주어진다.
출력#
JOI 군이 먹는 샤오롱바오의 맛있음의 합계의 최댓값을 1행으로 출력하시오.
🧐 관찰 및 접근#
- 생각보다 $N$도 작고, $D$는 더욱 작다.
- 뭔가 삘이 왔다. 지금 보고있는걸 먹을때 $D!$가지 경우의 수를 체크하는걸수도 있지 않을까?
- ㅁㄹ?? 되는지 모르겠네 짜봐야지
- 뭔가 삘이 왔다. 지금 보고있는걸 먹을때 $D!$가지 경우의 수를 체크하는걸수도 있지 않을까?
- 아이디어는 쉬운데 짜는게 되게 어려웠네;;;
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N;
rep(i, 0, N) cin >> D[i];
rep(i, 0, N) cin >> A[i];
map<vector<int>, int> perm_to_idx;
vector<vector<int>> idx_to_perm;
vector<int> v;
rep(i, 0, min(N, 7)) v.push_back(i);
do{
int tmp = 0;
vector<int> used(min(N, 7), false);
for(auto x: v){
used[x] = true;
rep(i, 0, min(N, 7)) if(!used[i] && abs(i - x) <= D[x]) tmp += A[x];
}
perm_to_idx[v] = idx_to_perm.size();
idx_to_perm.push_back(v);
DP[min(N, 7)-1][perm_to_idx[v]] = tmp;
}while(next_permutation(all(v)));
if(N < 7){
int ans = 0;
rep(j, 0, idx_to_perm.size()) ans = max(ans, DP[N-1][j]);
cout << ans << "\n";
return;
}
rep(j, 0, 5040) rep(pos, 0, 8){
vector<int> c_perm = idx_to_perm[j];
vector<int> n_perm;
rep(idx, 0, 7){
if(idx == pos) n_perm.push_back(7);
n_perm.push_back(c_perm[idx]);
}
if(pos == 7) n_perm.push_back(7);
vector<int> nn_perm;
rep(idx, 0, 8) if(n_perm[idx] != 0) nn_perm.push_back(n_perm[idx]-1);
int n_idx = perm_to_idx[nn_perm];
nperm[j][pos] = n_perm;
nperm_idx[j][pos] = n_idx;
}
rep(i, 7, N) rep(j, 0, 5040) {
vector<int> c_perm = idx_to_perm[j];
rep(pos, 0, 8){ // 만두 i를 언제 먹을것인가?
vector<int> n_perm = nperm[j][pos];
// 만두 i를 고려할 때 추가되는 값
int tmp = 0;
rep(idx, pos+1, 8){
int p = i - 7 + n_perm[idx];
if(abs(p-i) <= D[i]) tmp += A[i];
}
rep(idx, 0, pos){
int p = i - 7 + n_perm[idx];
if(abs(p-i) <= D[p]) tmp += A[p];
}
int n_idx = nperm_idx[j][pos];
DP[i][n_idx] = max(DP[i][n_idx], DP[i-1][j] + tmp);
}
}
int ans = 0;
rep(j, 0, 5040) ans = max(ans, DP[N-1][j]);
cout << ans << "\n";
}