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

전형적인 DP문제다.

처음엔 백트래킹으로 풀려했으나.. 개수가..너무 많아서

백트래킹을 어떻게 캐시로 저장할까하다가..

방향을 틀었다.

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

 

---

 

#처음 틀린풀이

#include<iostream>

using namespace std;

int N;

int card[1001];
int dp[1005][1005]; 
//카드를 살 때, 카드 수는 적되 가격은 높게 사야한다.
//현재 카드가 i개 가지고 있고 카드의 수와 가격을 보면서 골라야 한다.
//결국 다 뒤져봐야함

int M = -1; //최댓값

int x = 0;

int func(int cnt, int val){
    if(dp[cnt][x] > 0) return dp[cnt][x];
    
    //종료조건
    if(cnt > N)return 0;
    if(cnt == N){
        if(M<val){
            M=val;
        }
        return 0;
    }
    int ans;
    //N개를 중복되게 N번 고름.
    for(int i = 1; i<=N; i++){
        //선택
        ans = func(cnt+i, val+card[i]);   
    }
    x %= 1005;
    x++;
    return dp[cnt][x] = ans;
}


int main(){
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for(int i = 1; i <=N; i++){
        cin >> card[i];
    }
    
    func(0,0);
    
    cout << M;
    
    
    
}

 

아.. 백트래킹 자체가 중간 저장이긴 한데..아무튼

모르겠다.

 

#맞은 풀이

#include<iostream>

using namespace std;

int N;

int card[1001];
int dp[1005]; 
//N^2이면 백만번임.
//카드를 살 때, 카드 수는 적되 가격은 높게 사야한다.
//현재 카드가 i개 가지고 있고 카드의 수와 가격을 보면서 골라야 한다.
//결국 다 뒤져봐야함

//3장 사면 1,1,1/ 1,2 /3 의 가짓수가 있음

//4장 사면 1,1,1,1/ 1,1,2 / 1, 3 / 2, 2 가 있음
//살펴보면 3장에서 +1 하는 경우와 2장에서 + 2 하는 경우
//5장에선 1,1,1,1,1/ 1,1,1,2/ 1,1,3/ 1,4/1,2,2,/ 2,3/
//살펴보면 4장에서 + 1하는 경우, 3장에서 + 2하는 경우, 2장에서 + 3하는 경우가 있다.



int main(){
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for(int i = 1; i <=N; i++){
        cin >> card[i];
    }
    
    dp[1] = card[1];
    
    for(int i = 2; i<=N; i++){
        for(int j = 1; j<=i; j++){
            dp[i] =max(dp[i], dp[i-j]+card[j]); // dp[i]는 계속 최댓값으로 갱신
        }
    }
    

    
    cout << dp[N];
    
    
}

 

 

즉, dp[i]는 계속 갱신되고 이전 결과로부터 현재 어떤 카드를 가지는 것이 가장 좋은지 계속 갱신한다.

즉, 카드 4장을 사려면

카드 3장이 사는데 1,2장씩 사는게 가장 비싸게 샀다면

dp[3] = 1,2을 선택했다고할 수 있다.

그냥 dp[3]에서 1더하면 되는 것 아니냐? 할 수 있는데 그것이 아니다.

 

하지만 dp[3] 에서 1장을 살지 dp[2] 에서 2장짜리를 살지 dp[0]에서 4장짜리를 살지 구분해야한다.

다시 말해서 dp[4]를 구하기 위해선 1,1,2가 좋은지 2,2가 좋은지 4가 좋은지 알아야 한다.

즉, 이전 단계 모두에서 구해봐야 한다는 말이다.

그래서 계속 최댓값을 갱신해서 이전 결과를 구하게 된다.