[Algorithm]Baekjoon 2632번 :: 피자판매

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

2632번: 피자판매

int wantedSize, aPieceNum, bPieceNum;
vector<int> aPiecesInfo;
vector<int> bPiecesInfo;
 
int aDP[2000001] = { 0 };
int bDP[2000001] = { 0 };
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> wantedSize >> aPieceNum >> bPieceNum;
    
    int tempSum = 0;
 
    for (int i = 0; i < aPieceNum; ++i)
    {
        int a;
        cin >> a;
        aPiecesInfo.push_back(a);
        tempSum += a;
    }
 
    aDP[tempSum] = 1;
 
    for (int i = 0; i < aPieceNum - 1; ++i)
    {
        aPiecesInfo.push_back(aPiecesInfo[i]);
    }
 
    tempSum = 0;
 
    for (int i = 0; i < bPieceNum; ++i)
    {
        int a;
        cin >> a;
        bPiecesInfo.push_back(a);
        tempSum += a;
    }
 
    bDP[tempSum] = 1;
 
    for (int i = 0; i < bPieceNum - 1; ++i)
    {
        bPiecesInfo.push_back(bPiecesInfo[i]);
    }
 
 
 
 
    for (int i = 0; i < aPieceNum; ++i)
    {
        int sum = 0;
 
        for (int j = i; j < i + aPieceNum-1; ++j)
        {
            sum += aPiecesInfo[j];
 
            if (sum > wantedSize) break;
 
            aDP[sum] += 1;
        }
    }
 
    for (int i = 0; i < bPieceNum; ++i)
    {
        int sum = 0;
 
        for (int j = i; j < i + bPieceNum-1; ++j)
        {
            sum += bPiecesInfo[j];
 
            if (sum > wantedSize) break;
 
            bDP[sum] += 1;
        }
    }
 
    int answer = 0;
 
    answer = aDP[wantedSize] + bDP[wantedSize];
 
    for (int i = 1; i < wantedSize; ++i)
    { 
        if (aDP[i] >= 1 && bDP[wantedSize - i] >= 1)
        {
            answer += aDP[i] * bDP[wantedSize - i];
        }
    }
 
    cout << answer;
 
    return 0;
}

 

먼저 조건에 맞게 각 부분집합을 뽑아야 한다. 

여기서 조건이란, 반드시 인접해야 하며, 부분집합의 합은 판매할사이즈보다 작아야한다는 것이다.

그리고 조심해야할 것은 결국 원형이라는 것이다. 즉 벡터의 처음과 끝은 연결되어있다.

이부분을 처리하기위해 벡터에다가 0부터 size-1까지를 또 넣어줬다.

 

이후 0부터 기존 벡터의 사이즈만큼 인덱스를 하나씩 잡고 2중 반복문으로 부분집합을 만들텐데, 두번쨰 반복문의 시작인덱스는 당연히 i인데, 최대범위를 i + 벡터사이즈 -1 을 해야한다는 것이다. 

-1을 하는 이유는 피자판의 모든조각을 사용하는 부분집합을 제외시키기 위해서다.  제외시키지 않는다면 부분집합을 만드는 과정에서 모든조각을 사용하는 집합이 중복되서 나오게 된다.

 

그러니 해당 로직을 수행하기전에 미리 모든조각을 사용하는 경우를 DP에 저장한다.

그렇게 각각 A,B를 수행하고 일단 aDP[원하는 사이즈] + b[원하는 사이즈]를 answer에 더해준다.

그다음, A,B는 서로의 조각을 사용할 수 있기 때문에 1부터 원하는사이즈 -1까지 반복을 돌면서 서로 부족한부분의 조각합을 만들 수 있는 경우의수를 가져와서 곱해서 answer에 더해준다.

 

만약 원하는사이즈가 7이고, 이전의 로직을 통해 aDP[1] = 2; bDP[6] = 3; 이라면 이건 다음과 같이 설명된다.

A피자에서 1을 만들 수 있는 가짓수는 2가지이고, B피자에서 6을 만들 수 있는 가짓수는 3가지이다.

그러면 최종적으로 A,B 두 피자를 통해 7사이즈의 피자조각을 만들 수 있는 경우의 수는 

2 (A피자에서 1을만들 수 있는 가짓수) * 3 (B피자에서 6을 만들 수 있는 가짓수) = 6    이라는 값이 도출된다.