백준, BOJ, 12865번 C++ [CPP]

음

아주 어렵진 않지만 생각하기 어려운 문제다.

 

https://www.acmicpc.net/problem/12865

 

---

 

#맞은 풀이

#include<iostream>

using namespace std;

//가장 가치가 크게 해야함. 가장 큰 무게가 가장 큰 가치를 보장하지 않음
//모든 것을 보고 넣을 지 말 지 정해야 함. (Brute Force지만).. 정말 다조사하면 시간초과남
//똑똑하게 조사해야함. 2^100 연산이 필요. 캐싱 필요( 값 저장)


// 담을 수 있는지, 없는지
// 담을 수 있다면 담는 것이 좋은지, 아닌지 


int weight[101]; // 무게
int value[101]; // 가치
int N,M; // 개수, 최대무게

int dp[102][100001]; // 값 저장


//재귀를 이용한 풀이 (포함할 지를 결정해서 N번 반복 2^N)
//현재 조사한 개수, 현재 무게
int func(int idx, int w){
    
    //해당 index까지 조사한 결과가 있다면 바로 return -> dp이용 (2^N을 줄임)
    if(dp[idx][w] > 0){
        return dp[idx][w];
    }
        
    //N개 다 조사하면 종료
    //N이 1~100까지니까 N이 100이면 101되면 종료
    if(idx == N+1) return 0;
    
    
    //1. 현재 것 넣기
    int cur1 = 0;
    //넣으려는 무게와 현재까지의 무게를 더했을 때, 제한보다 작거나 같아야 넣을 수 있음
    if(w + weight[idx] <= M){
        cur1 = func(idx+1, w+weight[idx]) + value[idx]; // idx까지의 가치 = 이전 가치 + 이번에 넣는 물건의 가치
    }
    
    
    //2. 현재 것 넣지 않기
    int cur2 = func(idx+1, w); // idx까지의 가치 = 이전가치
    
    
    //결국 위의 재귀에서 N번이 시행되어서 아래 결과가 나온 것이다.
    return dp[idx][w] = max(cur1, cur2); // 넣는 것과 넣지 않는 것 중 큰 값 return
}


int main(){
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    //입력받음
    cin >> N >> M;
    
    //무게 가치 입력
    for(int i = 1; i<=N; i++){
        cin >> weight[i] >> value[i];
    }
    
    
    int ans = func(1,0); // 첫번째 물건부터 조사시작, 아무것도 안 넣은 가방 무게 0
    cout << ans;
    
    
}

 

 

위에 주석을 보다시피

어차피 그리디로 풀 수 없고

모든 것을 계산해봐야하는 문제다.

넣을 지 말지 계산해봐야하고

이를 연산횟수를 줄이기 위해서 캐싱을 이용할 뿐이다.

 

재귀를 이용하여 전체 모든 것을 조사했다.

포함, 미포함 -> 2가지로 각각 N번 시행

2^N 연산횟수

 

캐싱을 이용해 해당 idx에서 해당 w의 값을 최댓값을 저장할 수 있다.

 

근데 여기서 의문점...?

 

해당 DP테이블에 저장된 값이 쓰이나?

즉, 계산된 결과가 다음 계산을 위해 쓰이나??

쓰인다. 특히 무게가 초과했을 때 쓰인다.

 

아래 값을 넣어보면

8 4

1 3

1 6

1 3

1 3

1 3

1 2

1 5

1 8

 

대충 아래와 같이 무게가 초과했을 때

결과가 쓰이는 것을 볼 수 있다.