[AtCoder] Filling 3x3 array

https://atcoder.jp/contests/abc256/tasks/abc256_c

C - Filling 3x3 array

 

각 행과 각 열의 합이 정해져있으므로 만약 행과 열마다 2개 요소가 정해지면 나머지 하나의 요소의 값은 정해지는 구조이므로 N은 최대 30이고, 시간복잡도는 $O(N^4)$으로 그리 크지 않다. 

 

#include <iostream>
#include <algorithm>

using namespace std;
int h[3];
int w[3];
int arr[3][3];

int main() {
    int cnt = 0;
    for(int i = 0;i < 3;i++) {
        cin >> h[i];
    }
    
    for(int i = 0;i < 3;i++) {
        cin >> w[i];
    }
    
    int max_val0 = h[0] - 2;
    for(int i = 1;i <= max_val0;i++) {
        arr[0][0] = i;
        for(int j = 1;i + j <= h[0] - 1;j++) {
            int k = h[0] - i - j;
            arr[0][1] = j;
            arr[0][2] = k;
            
            int max_val1 = h[1] - 2;
            
            for(int i = 1;i <= max_val1;i++) {
                arr[1][0] = i;
                for(int j = 1;i + j <= h[1] - 1;j++) {
                    int k = h[1] - i - j;
                    arr[1][1] = j;
                    arr[1][2] = k;
                    
                    int max_val2 = h[2] - 2;
                    
                    for(int i = 1;i <= max_val2;i++) {
                        arr[2][0] = i;
                        for(int j = 1;i + j <= h[2] - 1;j++) {
                            int k = h[2] - i - j;
                            arr[2][1] = j;
                            arr[2][2] = k;
                            
                            if(arr[0][0] + arr[1][0] + arr[2][0] == w[0]
                               && arr[0][1] + arr[1][1] + arr[2][1] == w[1]
                               && arr[0][2] + arr[1][2] + arr[2][2] == w[2]){
                                cnt++;
                            }
                        }
                    }
                }
            }
        }
    }
    
    cout << cnt << '\n';
    
}