[프로그래머스/C++] 안티세포

문제

문제 설명

 

 

풀이

 

이 문제를 처음 봤을 때 어떻게 풀지 많이 고민했다.

 

모든 경우를 계속해서 계산하기에는 너무 계산이 많아졌기 때문에 이전에 계산된 내용을 이용해 빠르게 문제를 풀 수 있을 것 같았다.

 

고민 후에 DP와 Map을 이용해 문제를 해결했다.

 

[문제 풀이]

 

안티세포 X와 Y에 들어 있는 수 들을 아래와 같이 표현한다고 가정하자

$$ Y\,=\,(i_{ys},\, ...\, i_{ye})$$

$$ X\,=\,(i_{xs},\, ...\, i_{xe})$$

여기서 안티세포 Y와 X의 합이 같아서 합쳐진다면 합쳐진 새 안티세포 N은 아래와 같이 표현할 수 있다.

$$ N\,=\,(i_{ys},\, ...\, i_{xe})$$

이제 N의 왼쪽에 있는 안티세포를 생각하면 아래와 같이 표현할 수 있다.

$$ M\,=\,(i_{ms},\, ...\, i_{ys-1})$$

 

여기서 중요한 점을 알 수 있다.

임의의 안티세포를 X라고 하고 X의 첫 원소를 X_s라고 하면 X와 합칠 수 있는 안티세포의 마지막 원소는 X_(s-1) 이라는 것이다.

 

이를 이용해 다음과 같이 DP를 정의할 수 있다.

DP[i]의 정의는 첫 원소부터 i번째 index까지 배열이 주어졌을 경우 만들 수 있는 서로 다른 배열 c의 개수다.

(단, 공집합의 개수는 제외)

 

이 정의를 이용해 아래의 예를 해결해 보자

 

배열 b=[1,1,1,1] 인 경우다.

 

정의에 의해서 DP[0]=0이다.

그렇다면 DP[1]은 어떻게 구해야할까?

b의 첫 원소와 두 번째 원소가 1, 1 로 같으므로 합칠 수 있다. c = [(1,1)]

그러므로 DP[1]=1이다.

 

이제 DP[2]를 구해보자

DP[2]는 c = [(1,1),1], [1,(1,1)]이므로 DP[2]=2이다.

 

여기서 DP[2]를 다르게 표현할 수 있다.

DP[2]=DP[1]+[2의 원소와 합칠 수 있는 경우]

 

DP[1]은 정의에 의해 쉽게 이해가 되지만 [2의 원소와 합칠 수 있는 경우]는 이해가 잘 가지 않을 수 있다.

 

이제 b = [1, 1, 1]을 이용해 예를 들어 보자

2번째 인덱스의 바로 왼쪽에 올 수 있는 수들은 어떤 수들이 있을까?

답은 1과 2다.

 

1이 올 수 있는 경우는 당연히 아래와 같이 나눠진 경우다 c = [(1), (1), (1)]

즉, c의 안티세포를 a, b, c라고하면 b가 1이 되는 경우다.

 

2가 올 수 있는 경우는 무엇이 있을까?

c=[(1, 1),(1)]와 같이 0번 index와 1번 index가 합쳐진 경우다.

 

이처럼 왼쪽에 어떤 수가 올 수 있는지를 알면 DP를 쉽게 계산 할 수 있다.

map을 활용해 [왼쪽에 올수 있는 수 : 몇 번째 인덱스부터 더해야하는지] 를 저장해 두면 O(1)로 찾을 수 있다.

 

이를 이용하면 DP[2]=DP[1]+1 이 됨을 알 수 있다.

 

그러므로 Map은 vector<map<안티세포의 합, index>> 으로 정의하자.

 

똑같은 방법으로 DP[3]을 구할 수 있다.

 

더 이해가 쉽도록 그림으로 표현하면 아래와 같다.

3번 index의 값은 1이다.

 

이제 2번 index를 포함해 만들 수 있는 안티세포가 1이 될 수 있는지 Map에서 찾는다.

 

Map에는 1의 값을 갖는 안티세포는 2번 index~2번 index까지의 안티세포를 합친 값이 1이라는 사실이 저장되어 있다.

그러므로 이 안티세포와 합칠 수 있으며, 합친 이후에 왼쪽에 오는 수들은 1번 index를 포함한 수가 온다.

 

마찬가지로 1번 index를 합친 안티세포는 0번 index~1번 index까지의 안티세포를 합쳐서 2를 만들 수 있다는 게 Map에 들어있다.

 

그러므로 두 세포를 합쳐서 4의 값을 갖는 안티세포를 만들 수 있다.

4의 값을 갖는 안티세포의 왼쪽에 오는 수는 없으므로, 탐색을 종료하면 된다.

 

이러한 과정을 아래와 같이 표현할 수 있다. 

이렇게 DP의 모든 값을 구하면, 5라는 값을 구할 수 있고 마지막에 공집합의 개수 1을 더해주면 답인 6이 나온다.

 

이렇게 DP를 이용해 구할 수 있는 이유는 서로 인접한 안티세포만 더할 수 있으며, 더한 후의 값이 2배가 되기 때문이다.

 

즉, c의 배열을 구하는 과정이 연속된 두 값이 같은지 판별하는 것이다.

 

 

​

[아이디어 정리]

1. DP[i]를 i번째 index까지만 존재하는 배열일 경우 만들 수 있는 c 배열의 수로 정의한다. (공집합 제외)
2. DP[i]=DP[i-1]+[i번째 수를 더해서 만들 수 있는 경우의 수] 로 정의하고 계산한다.
3. Map[j][num] = idx 로 idx ~ j번째 수를 더할 수 있으며, 더한 값이 num으로 정의한다.
4. i번째수의 왼쪽에 올 수 있는 수 중에서 i번째 수와 같은 값이 있는지 Map에서 찾고 있다면, 그 수만큼 더한다.
5. 모든 경우의수를 구했다면, DP[i] 값을 갱신한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <map>
using namespace std;


long long reDP(vector<long long> &newV, vector<map<long long, long long>> &numMap, vector<long long> &DP, int nowDP);

long long calcMap(vector<map<long long, long long>> &numMap, int stIdx, vector<long long> &newV, vector<long long> &DP)
{
    long long tempIdx=stIdx;
    long long nowNum=newV[stIdx]; 
    long long retAns=0;
    numMap[stIdx][nowNum]=tempIdx;
    tempIdx-=1;
    while(true)
    {
        if (tempIdx>=0&&numMap[tempIdx][nowNum]!=0)
        {
            tempIdx=numMap[tempIdx][nowNum];
            nowNum*=2; // 수가 합쳐지면 2배가 된다.
            numMap[stIdx][nowNum]=tempIdx;
            tempIdx-=1;
            retAns+=1; // 경우의 수 더하기
            retAns+=reDP(newV, numMap, DP, tempIdx); // DP[tempIdx]의 경우의 수
            retAns%=1000000007;
        }
        else 
        {
            return retAns;
        }
    }
    return retAns;    
}

long long reDP(vector<long long> &newV, vector<map<long long, long long>> &numMap, vector<long long> &DP, int nowDP)
{
    if (nowDP<=0) // 왼쪽에 수가 없다면 0을 return
    {
        return 0;
    }
    if (DP[nowDP]!=0)
    {
        return DP[nowDP];
    }
    DP[nowDP]=reDP(newV, numMap, DP, nowDP-1);
    DP[nowDP]+=calcMap(numMap, nowDP, newV, DP);
    DP[nowDP]%=1000000007;
    return DP[nowDP];
}

vector<int> solution(vector<int> a, vector<int> s) {
    vector<int> answer(s.size(),0);
    int pre=0;
    for (int tc=0; tc<s.size(); tc++)
    {
        vector<long long> newV(s[tc]);
        for (int i=0; i<s[tc]; i++)
        {
            newV[i]=a[pre+i];
        }
        pre+=s[tc];
        vector<map<long long, long long>> numMap(s[tc]); //몇번째 index까지 합쳐질 수 있는지 저장
        vector<long long> DP(s[tc],0); // 0~i번째 수로 만들 수 있는 c배열의 수를 저장(공집합 제외)
        numMap[0][newV[0]]=1;
        answer[tc]=reDP(newV, numMap, DP, s[tc]-1)+1;
    }
    return answer;
}

 

---

문제를 풀기 전에 많은 고민을 했다.

고민을 하고 문제를 풀었기 때문에 이 글의 설명에는 index i를 c배열에 추가하는 과정이 생략되어 있다.

(왜냐하면 index i를 c배열에 추가해 만드는 게 안티세포들을 합칠 수 있는지 판단하는 과정과 같기 때문이다)

 

또한 DP를 재귀적으로 구했는데 나중에 생각해보니 굳이 재귀로 구할 필요 없이 순차적으로 구하면 됐다...

풀이를 고민하는데 시간이 필요한 문제였고, 푸는데는 시간이 오래걸리지 않았다.

그리고 설명하는 게 가장 시간이 오래 걸렸다...

프로그래머스