[Leetcode 465번 문제] 465. Optimal Account Balancing

문제 상황

You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.

Return the minimum number of transactions required to settle the debt.

transactions 배열이 주어진다 각 요소는 a부터, b까지 c만큼 라는 뜻, a, b 는 ID고 c는 달러다.

debt를 내지 않기 위해서 필요한 가장 작은 transaction의 수를 구하여라

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

다음의 경우를 보면 1이 0한테 10달러를 빚졌고 0이 2한테 5달러를 빚졌다. 그래서 결과적으로 1이 0과 2한테 5달러씩 주는것.

Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.

0이 1한테, 1이 0한테, 1이 2한테, 2가 0한테 각각 얼마씩 주고있음 그래서 퉁치기 식으로 1이 0한테 4달러 주는걸로 해결한다면 문제가 해결된다.

 

입력

• 1 <= transactions.length <= 8
• transactions[i].length == 3
• 0 <= fromi, toi < 12
• fromi != toi
• 1 <= amounti <= 100

출력

가능한 가장 짧은 길이의 정수 최대는 8 최소는 0

과정

그니까 이게 대신 내주는 방법이 여러가지가 있을건데

상황 구현의 문제가 있다.

• 합치는건 한개의 간선에 대해서, 여러가지가 경우가 있을 수 있다.
• 그러니 합칠간선이 있으면 합친다.
• 근데 모든상황을 카테고리화하는건 어떻게 ? 모델화하는것을 말하는거지 정확하게는

초기상황으로 가능한 모든 경우의 수 만 있다면 충분할까?

dp의 한 칸을 [13][13]이라고 할 수는 있겠다. x가 y에게 얼마를 주어야하는지를 나타내는 표로써,

그런데 문제는, 이게 몇번이 일어나야 하냐는것. 최대 몇번?

아마도 한번 할때마다 선은 줄어들을거다. 그건 맞음 근데 그렇다고해서 그게 8개로 퉁쳐지는건 아니다.

1 → 2 , 2 → 3을 합친거랑

2 → 4, 4 → 3을 합친거랑 어떻게 구분을 해야하는지도 모르고 x에서 y로, y에서 z로 갔다라는거 자체를 어떻게 표현할지

12 * 12 * 12 * 8

144 * 96 * 144

최대 줄어들 수 있는 횟수 자체는 8이라고 봐야하고, 모든 이동할 수 있는 경우의 수가, x(0 ~ 11) 에서 y(0 ~11) 을 거쳐 z(0 ~ 11)로 라는 횟수가 만들어지기 때문에 이거라면 겹치지 않고. 그럼 12을 돌면서 얘가 겹치는 모든애를 찾아도, 큰 문제는 없겠지 근데 줄어들지 않는경우의 수도 있는데.

하지만 중간에 줄어들지 않는 경우도 있었다. 한번은 안줄어들고 계속 돌아야줄어든다는 거잖아. 이럴때를 어떻게 하냐는거야

계속 뱅뱅돌수 있나? 적어도 뱅뱅 돌수는 없음.

3개 + ā 의 노드가 있음, 이들이

누가 더 크냐에따라서 다른데 , 만약에 가는 화살표가 클경우엔, 아예

모델 만들기가 상당히 빡센문제다, 언제 끝나는지를 알 수가 없으니까.

내가 실패한 알고리즘

class Solution {
    int dp[100][1728][12][12];
public:
    int minTransfers(vector<vector<int>>& transactions) {
        auto transform = [](int a, int b, int c){
            return 144 * a + 12 * b + c;
        };  

        for (vector<int> transaction : transactions)
        {
            dp[transaction[0]][transaction[1]][0][0] = transaction[2];
        }
        int ans = 8;
        for (int tim = 0; tim < 56; tim++)
        {
            for (int cas = 0; cas < 1728; cas++)
            {            
                int cnt = 0;
                for (int i = 0; i < 12; i ++)
                {
                    for (int j = 0; j < 12; j++)
                    {
                        if (dp[tim][cas][i][j])
                        {
                            cnt++;
                            int remains = dp[tim][cas][i][j];
                            for (int k = 0; k < 12; k++)
                            {
                                if (dp[tim][cas][j][k])
                                {
                                    
                                    if (dp[tim][cas][i][j] > dp[tim][cas][j][k])
                                    {
                                        // dp[tim + 1][transform(i, j, k)][i][j] -= dp[tim][cas][j][k];
                                        remains -= dp[tim][cas][j][k];
                                        dp[tim + 1][transform(i, j, k)][i][k] += dp[tim][cas][j][k];
                                    }
                                    else
                                    {
                                        dp[tim + 1][transform(i, j, k)][i][k] += dp[tim][cas][i][j];
                                        dp[tim + 1][transform(i, j, k)][j][k] -= dp[tim][cas][i][j];
                                        // dp[tim + 1][transform(i, j, k)][i][j] = 0;
                                        remains = 0;
                                    }
                                }
                                dp[tim + 1][transform(i, j, k)][i][j] = remains;
                            }
                        }
                    }
                }
                if (cnt)
                {
                    ans = min(ans, cnt);
                }
            }
        }
        return ans;
    }
};

난 결국 이문제를 풀지 못했다. DP는 각 작은 상황별로 이 상황이 영향을 받는 상황, 이 상황이 영향을 줄 상황을 분리할 수 있어야하는데 그렇게 하지 못한 것이다.

나는 DP의 한 단위를 [i][j] 12 * 12로 하려했고, 모든 경우의 수를 구분하기 위해 [i][j][k] 12 * 12 * 12에 회차 [100] 을 곱해서 구하려했다. 이미 초기화된 수준이라고 봐야겠지만 그게 떠올릴 수 있는 유일한 방법이었다.

1. [i][j] 가 하나의 판이기 때문에.
2. [i][j][k] * 100이 서로의 판을 구분짓는 역할이라고 생각했기 때문에
3. 하지만 문제는 풀 수 없었고 , 어디가 문제였는지를 찾아야한다 이제
4. 알고리즘과 나 사이에 어떤 벽이 있는것 같다.

혼자서는 세상을 구할 수 없다.

class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        unordered_map<int,int> mp;
        for(auto transaction: transactions){
            mp[transaction[0]]-=transaction[2];
            mp[transaction[1]]+=transaction[2];
        }
        // 맵을 통해서 +와 -를 계산해놓음.
        

        vector<int> netTransfer;

        for(auto [_,amount]: mp)if(amount)netTransfer.push_back(amount);
				// 구조분해 할당을 통해 amount가 있다면 뭔지모를 배열에 추가
				
				
        int n = netTransfer.size();
        // n의 크기를 설정, amount가 0인걸 mp를 제외한 node들을 설정
        vector<int> memo(1<<n, -1);
        // 그 n을 기반으로 가능한 모든 경우의 수 벡터 생성
        memo[0] = 0;
        // 0은 0
        
				// 마스크라는건 아마 모든 경우의수 1부터 255까지의 모든 경우의 수.
				// 한개의 마스크가 의미하는 건 뭐지? 
        for(int mask = 1;mask<(1<<n);mask++){
            int totalSum =0;
            int groups = 0;
            // group은, 한개의 마스크에서 특정노드가 켜져있음을 상징할 때
            for(int i=0;i<n;i++){
                if((mask&1<<i)!=0){
		                // 그 마스크 값이라는게 1이라면. 뭔가 현존하는 값이라면
		                //그 번호의 netTransfer을 더한다
                    totalSum += netTransfer[i];
                    // 그 노드의 netTransfer을 더하고 
                    groups=max(groups, memo[mask^1<<i]);
                    // 같은 마스크중 이 1의자리수가 뒤집혀져있는 마스크와 , 나 자신간의 값중 큰것을 groups로 선택
                }
            } 
            // 현재 마스크의 값을 가능한 큰값을 설정된 groups에 에러시 1을 더하는 방식으로 내 마스크에 설정
            memo[mask] = groups+ (totalSum==0?1:0);
        }
        // 리턴하는 값은 아마도, 모든 수가 1인,
        // memo의 값들은 그룹 + (netTransfer을 더한 값 + i번쨰 요소값이 뒤집혀져 있는 경우의 값의 최대값을 의미한다)
        // 그리고 totalSum이 0이야, 즉 한번도 더해진적이 없어, 그러면 1개가 있겠다하고 1로 설정해놓는다. 왜? 
        // 그리고는 모두가 켜져있었을때의 값을 리턴함.
        return n-memo[(1<<n)-1];
        // 모든 노드가 1이었을때의 memo 값을 n에서 뺀다. 
    }
};

groups는 mask&1<<i 가 참이라고 전해지면, max(groups, memo[mask^1<<i]) 마스크를 뒤집은채로 max값을 구한다. 당연히 저건 없었을때로 고정이다. mask가 1일경우엔 0과 부딪힌다. totalsum이 뭘 의미할까.

Our task is now to find maxium num of groups in array such that net of the group is zero.

For each group of size g we will have g-1 transactions. Min transactions would be: n - number_of_groups.

이 문제의 풀이에 따르면 돈 교환의 총합이 0이되는 그룹을 찾아내기 위해서이다.

각 mask의 요소의 뜻은?

mask는 살아남은 각각의 노드를 비트로 표현한 것을 뜻한다. 비트가 노드를 상징하는 것이다.

Groups는 뭘 의미하는가

1부터 최대 4047 까지 갈 수 있는 마스크가 있고 이건 그냥 각각의 비트들이 묶여있을때 그냥 왔다갔다는 다 무시하고 총합이 0인지만 보는 것이다. 만약에 서로 합쳐진 그 요소들의 총합이 0이라면 이들은 한개의 그룹이라는 뜻이 된다.

mask의 group은 totalSum이 0일때 처음 양의 정수가 될 것이다. 한 마스크의 그룹은, 그 마스크와 한개의 비트가 0으로 다른 마스크와 기본적으로 같은 group일 것이다. (아직 계산을 하지 않았을 때) group의 개수가 정해져있고 group의 일부가 평형을 이루었는데 새로운 노드가 들어오기만 한 상황이라면 (다른 평형을 찾지 않는 상황) group의 개수는 동일하다. 그런데 이 모든 노드의 합이 또 평형을 이룬다면? group의 값에 1을 더한다

왜 Group의 값에 1을 더하냐

일단 n명의 인원이 평행을 이루고있다면 이들이 교환하면 되는 횟수는 n - 1로 정해진 것 같다 여기에 대해서는 아직 난 확신이 없다. 그렇다는 생각이 들기는한다. 어쨌든 그럼 평형을 이루는 group이 생길수록 총 교환횟수는 n에서 1씩 준다고 봐도 될 것이다. 그렇기 때문에 이전마스크에서 group의 최대값을 가져오고 새 마스크가 평형을 이룰경우 또 1을 더하는 것으로 보인다.

이 문제는 이것에 답해야한다 왜 DP였나?

결국 이 문제가 왜 DP였는지 모른다면 난 이문제를 다시 풀 수 없다. 그걸 위해서 왜 이문제가 DP인지를 연구할 필요가 있다.

이 문제의 가장큰 패착은 내가 선후관계를 노드 a와 b의 연결로봤다는 것이다. 근데 이문제는 전혀 그래프 문제도 아니었다. 얼핏 a가 b한테 선을 뻗는 그래프 문제로 보이지만 실제는 그래프와 관련없고 오히려 간단하게 한 노드별 총합으로 치환해야하는 문제였다.

그리고 진정한 직렬화는 그룹화하는 마스크에 있었다. 노드 k개의 상태를 고려한 마스크는 k - 1개를 고려하고있는 각각의 이전 k 개의 노드 그룹과 그룹이 1개 많거나 같다. 1개 더 많은 기준은 총합이 0인가에 대한 기준, 그러면 직렬화와 영향그래프를 그릴 수 있다. 정말 어려운 문제였다. 언제 다시 풀지 정해야 할 것