[SWEA / C++] 8935번 : 스팟마트

DP - 테이블을 역으로 채워가는 발상

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW5jNL968dwDFATQ

비슷한 문제 : https://www.acmicpc.net/problem/10777

문제 설명

인재개발원 스팟마트에서 과자를 무료로 나눠주는 행사를 진행하고 있다!

스팟마트에는 N봉지의 과자가 좌에서 우로 나열되어 있으며, 이 중 i번째 봉지는 Ai개의 조각을 가지고 있다.

추가적으로 M개의 봉지가 더 제공되며, 이 중 i번째 봉지는 Bi개의 조각을 가지고 있다.

당신은 좌에서 우로 나열되어 있는 N봉지의 과자 사이에 M개의 봉지를 아무 곳에나 (시작점, 끝점, 봉지 사이) 끼워 넣을 수 있다.

이렇게 되면 N+M 개의 봉지가 좌에서 우로 나열되며, 그 중 초기의 N 봉지는 상대적 순서를 유지하는 형태가 될 것이다.

당신은 이렇게 만들어 놓은 리스트를 좌에서 우로 순서대로 걸어가면서 뽑아간다.

리스트에 있는 과자를 고를 수도 있고, 안 고를 수도 있지만, 행사의 규칙에 의하면 과자 한 봉지를 가져갔다면 그 다음 과자 봉지는 절대 가져갈 수 없다.

다른 말로 하면, 리스트에서 연속된 과자를 고를 수 없다.

가장 많은 과자 조각을 가져갈 수 있는 방법은 무엇일까?

입력

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다.

이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다.

각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 3,000)

이후 N개의 줄에 Ai가 주어진다. (1 ≤ Ai ≤ 100,000)

N+2번째 줄에는 M이 주어진다. (0 ≤ M ≤ 100)

이후 M개의 줄에 Bi가 주어진다. (1 ≤ Bi ≤ 100,000)

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

각 테스트 케이스마다 한 줄씩, 최대로 가져갈 수 있는 과자의 개수를 출력하라.

해결 방향

dp[n][m][discard][chosen]

• n : N봉지의 과자 중에서 n번째 과자
• m : M봉지의 과자 중에서 선택한 개수
• discard : M봉지의 과자 중에서 버린 개수
• chosen : N봉지의 직전 과자를 선택하였는지 여부

참고 코드

https://suhwanc.tistory.com/193

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
using namespace std;
 
//dp[n_i][m_i][skip][get]
//n_i : n봉지의 과자 중 n_i번째를 보고있는 상태(0과 n은 각각 왼쪽 끝, 오른쪽 끝을 의미한다.
//m_i : m봉지의 과자 중 고른 과자의 수
//skip : m봉지 중 스킵한 개수
//get : 위 상태일 때 바로 직전에 과자를 get했는가 (했으면 1)
int dp[3001][101][101][2];
 
vector<int>vn, vm;
int n, m;
int go(int n_i, int m_i, int skip, int get){
    //만약 n봉지 끝까지 갔고 && m봉지도 끝까지 간 경우(고른 과자 + 스킵 과자)
    if(n_i == n && m_i + skip == m) return 0;
    
    int &ret = dp[n_i][m_i][skip][get];
    if(ret != -1) return ret;
    
    ret = 0;
    
    //고르지 않은 경우
    if(get == 0){
        //만약 n봉지를 다 고르지 않은상태일때
        if(n_i < n){
            ret = max(ret, go(n_i + 1, m_i, skip, 1) + vn[n_i]); //고르거나
            ret = max(ret, go(n_i + 1, m_i, skip, 0)); //고르지 않거나
        }
        //만약 m봉지를 다 고르지 않은상태일때
        if(m_i + skip < m){
            ret = max(ret, go(n_i, m_i + 1, skip, 1) + vm[m_i]); //고르거나
            ret = max(ret, go(n_i, m_i, skip + 1, 0)); //고르지 않거나
        }
    }
    //이미 고른 경우 -> 어디를 스킵할까?
    else{
        //만약 n봉지를 다 고르지 않은상태일때
        if(n_i < n){
            ret = max(ret, go(n_i + 1, m_i, skip, 0)); //고르지 않거나
        }
        //만약 m봉지를 다 고르지 않은상태일때
        if(m_i + skip < m){
            ret = max(ret, go(n_i, m_i, skip + 1, 0)); //고르지 않거나
        }
    }
    return ret;
}
int main(int argc, char** argv) {
    int t; cin>>t;
    int num = 1;
    while(t--) {
        cin>>n;
        vn.resize(n+1);
        for(int i=0; i<n; i++) cin>>vn[i];
        
        cin>>m;
        vm.resize(m+1);
        for(int i=0; i<m; i++) cin>>vm[i];
        vm[m] = -987654321;
        sort(vm.begin(), vm.end(), greater<int>());
        
        memset(dp, -1, sizeof(dp));
 
        cout<<"#"<<num<<" "<<go(0, 0, 0, 0)<<"\n";
        num++;
    }
    return 0;
}

내 코드

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>

#define MAX_N 3001
#define MAX_M 101

using namespace std;

// dp[N의 idx][M의 idx][버린 M 개수][직전 선택 여부]
int dp[MAX_N][MAX_M][MAX_M][2];

int N,M;
int listN[MAX_N],listM[MAX_M];

void init(){
    memset(dp, -1, sizeof(dp));
    sort(listM,listM+M,greater<int>());
}

int take(int n, int m, int discard, int chosen){
    // 유효범위가 아닌 경우 0 반환
    if(n == N && m+discard == M)
        return 0;

    int &result = dp[n][m][discard][chosen];

    if(result != -1)
         return result;

     result = 0;

    // 직전 과자가 선택된 경우
    if(chosen == 1){
        // N 리스트에서 과자가 남은 경우
        if(n < N){
            result = max(result, take(n+1,m,discard,0)); // 선택할 수 없음
        }
        // M 리스트에서 과자가 남은 경우    
        if(m+discard < M){
            result = max(result,take(n,m,discard+1,0)); // M봉지를 하나 버림
        }
    }
    // 직전 과자가 선택되지 않은 경우 선택 가능
    else{
        // N 리스트의 과자가 남아있음
        if(n < N){
            result = max(result, take(n+1,m,discard,1) + listN[n]); // N 리스트에서 하나 선택
            result = max(result, take(n+1,m,discard,0)); // 선택하지 않음
        }
        // M 리스트의 과자가 남아있음
        if(m+discard < M){
            result = max(result, take(n,m+1,discard,1) + listM[m]); // M 리스트에서 하나 선택
            result = max(result, take(n,m,discard+1,0)); // M봉지를 하나 버림
        }
    }   

    return result;
}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    
    scanf("%d",&T);
    
    for(test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d",&N);
        for(int i=0;i<N;i++)
            scanf("%d",&listN[i]);

        scanf("%d",&M);
        for(int i=0;i<M;i++)
            scanf("%d",&listM[i]);        

        init();        

        printf("#%d %d\n",test_case,take(0,0,0,0));     
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

시행착오

• dp 테이블을 역으로 채워가는 아이디어의 발상

  한 케이스에서 만나는 경우들을 고려한 뒤 전체 케이스에 적용해보자

• fill 함수와 memset 함수의 속도 차이

  memset이 fill보다 훨씬 빠르다
  -> memset은 0 외에 -1은 초기화가 가능함!