백준26607 GOLD 3 시로코와 은행털기
Published:
익숙한 캐릭터가 보이기에 한번 풀어보게 되었다.
분류는
- dp
- 배낭 문제
로서, 배낭 문제 중 0/1 배낭문제를 풀어본뒤, 이에 도전하였다.
풀이 (잘못됨)
문제 정의 :
n명 중 k명을 뽑을 때, 각자의 힘수치 합 * 속도 수치 합을 최대화할때, ‘그 최대 값’을 구하기.subproblem 정의하기:
일단 조합 문제 ->
배낭문제 처럼 접근하기로 결정, 각 후보마다 강도 파티원에 끼울지 여부를 선택,
제약은 파티원이 k 명 제한이란 것. =>
dp[n,k] = n번째 후보까지 검토했을 때, k명이 강도파티에 합류한 케이스에서 (힘수치 합) * (속도 수치 합)이 최대일때의 값.
따라서 문제의 답은 dp[n,k].(모든 후보 검토한 k명의 파티원의 힘수치합, 속도수치 합이 최고인 케이스 일때의 값.)relation 정의하기:
dp[n,k]의 경우 일단 하나씩 선택해가는 방향으로 가니 dp[n-1,?]의 서브프라블럼들로 나뉠수 있음. 이번 후보를 스킵하고, 인원이 k라면 dp[n-1,k].
이번 후보를 참여시킨다면 dp[n-1, k-1] + <인원에 해당하는="" 총="" 스텟="" 증가=""> 이 될 것이다. (n-1 이하는 상관 x, 만약 가능했다면 dp[n-1,k]에 이미 반영, 할때 못떠올림 ㅠㅠ)
하지만 이는 제대로 작동하지 않았다. 왜냐하면
n명까지 고려했을때 k 인원일때 최대 값일 지라도, n+1명 째의 스텟을 해당 스텟에 합친다고해도 최대 값이 아닐 가능성!
ex)
| 이름 | 속도 | 힘 |
|---|---|---|
| 미도리 | 1 | 4 |
| 모브 | 2 | 3 |
| 모모이 | 4 | 1 |
(이외에도 여러 사람이 있으나, 예시 만들기 복잡해서 간단히)
이들이 선택지에 있다고하자. 모모이의 파티 합류여부를 i번째 결정해서 K 명을 만족시키려하자. 그러면 dp[i-1,K-1]을 참고할 것이다. 그러나 이경우에선 미도리의 스텟이 더해진뒤 곱할때, 최적이지 않기에 이미 파티 리스트에서 이미 제외되었다. (한쪽만 크니까)
그래서 미도리, 모모이가 참여하면 스텟을 합친 곱이 최대 치가 되지만 뒤의 선택을 고려하지 않고 k-1명 제한 조건에서 i-1번째 선택을 해서 미도리를 데려오지 못하고 모브를 데려왔기에 이때 모모이를 데려와도, 최적을 만들기위한 미도리를 다시 고려할 수 없어 이 subproblem은 답을 구할때 이용할 수 없게된다.
잘못된 풀이를 통해 알아가야 할 것 i번째 선택, k명 모집 상태에서 스텟을 연산해서 최고 값이 아닐지라도, 고려할 필요가있다. 이를 어떻게 모두 저장해서 이용할까?
올바른 풀이.
집중했어야 했던 포인트들
최대 값이 되는 조합이 아닌, 최대 값이되는 값만 알면됨. 그렇다면 i번째 k명까지 모집됐을때 스텟 값이 같다면, 누가 들어있던 상관없다. == 중복 제외하고 계산된 스텟 값들만 기억하자.
스텟의 합은 주어진다 == 하나의 스텟만 알면, 다른 스텟도 알 수있다.
2차원으로 부족하다면, 3차원 쓰기.
풀이 일단 개인의 스피드 = 개인 스텟의 합 제한- 스피드 이므로, 스피드 만을 이용한다
subproblem 정의: dp는 bool 배열이다. dp[i][j][z] = i번째 인원의 참여여부를 결정했을때 j명의 인원이고, 스피드값 계산 결과가 z인 경우가 존재한다. 답 = dp[i][j][x]가 참인것 중에서 (x)* (전체인원의 스텟의 합-x) 이 최대가 되는 경우.
relation 정의: 만약 인원이 추가 안되는 경우 dp[i-1][j][z]값 그대로 가져간다. 인원이 추가되는 경우 dp[i-1][j-1][z-
] 이 둘 중 하나가 true이면 true. dp[i][j][z] = dp[i-1][j][z] || dp[i-1][j-1][z- ] dependency = 바로뒤, 좌측 대각선위 이렇게 두칸. base case는 처음부터 쭉 아무것도 선택하지 않는 dp[*][0][0] = true. 아무도 안 택하면 당연히 스피드 총합은 0.
4.시간 복잡도. 베이스 케이스 초기화 : O(n) n * m * z사이즈 3차원 배열에서 한칸마다 계산 : O(n * m * z) 총 O(n * m * z)
풀이
#include <iostream>
#include <vector>
#include <tuple>
int n;
int k;
int sum;
std::vector<int> v;
bool dp[81][81][16001];
int main() {
for(int i = 0; i<= 80; i++) {
for(int j = 0; j<= 80; j++) {
for(int z = 0; z<= 16000; z++) {
dp[i][j][z] = false;
}
}
}
std::cin >> n >> k >> sum;
for(int i = 0; i<n; i++){
int temp1,temp2;
std::cin >>temp1 >> temp2;
v.push_back(temp1);
}
int limit = sum * k;
for(int i = 0; i<= n; i++) {
dp[i][0][0] = true;
}
//내가 처음에 0일때의 케이스는 문제 없도록 베이스케이스를 설정,
//뒤에 안 그렇게 됨. 그게 문제였었다.
for(int r = 1; r <= n; r++) { //r: 모든 인원 n 에 대해서 차례로 확인
int speed = v.at(r-1);
for(int c = 1; c<=k; c++) { //c: 현재 강도 파티원의 인원이 c인 경우
//bool isreal 원래 여기있었다. 그러나 이를 후에 갱신 안해줘, 한번 true되면 열 전체가 true되는 불상사 발생.
for(int z = 0; z <= c* sum ; z++) {//가능한 모든 수치값에 대하여 존재 가능 여부를 확인.
bool isreal = false;
if(z-speed >=0&& dp[r-1][c-1][z-speed] == true){
isreal = true;
}
if(dp[r-1][c][z] == true)
isreal = true;
dp[r][c][z] = isreal;
}
}
}
int max = 0;
for(int i = 0; i<= limit ; i++) {
if(dp[n][k][i] == false)
continue;
int speed = i;
int strength = limit-speed;
if (max < speed*strength)
max = speed*strength;
}
std::cout << max;
}
느낀점
- 서브프라블럼 자체로는 최적값일 수 있으나, 이들간 계산을 통해 만들어진 값이 최적일지 확실치 않다면 꼭 의심하라.
