4348번 막대 정사각형

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

캐시 cache dp 다이나믹 동적 계획 복습 코테 boj 백준 코딩 필수 bit 비트마스크

전체 총 합(sum)이 4로 나누었을 때 나머지가 있다면 no이다.

반례 :

2

5 2 2 2 2 1

5 2 2 2 2 2

나머지가 없다면(=0), dfs를 통해 len에 v[i]를 더해가면서 sum / 4를 기준으로 조건을 나누어서 처리를 한다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 22
 
int n, sum;
bool cache[1 << Max];
vector<int> v;
 
bool dfs(int path, int len)
{
    if (path == ((1 << n) - 1)) {
        // 모든 막대를 사용했다면
        return true;
    }
 
    if (cache[path]) {
        // 이미 사용된 path라면
        return false;
    }
    cache[path] = true;
 
    for (int i = 0; i < n; i++) {
 
        // 이미 사용된 막대이거나 
        // 현재 i번 째 막대 길이와 len의 합이 전체 총합의 1/4을 초과한다면 무시
        if ((path & (1 << i)) || len + v[i] > sum / 4) {
            continue;
        }
 
        if (len + v[i] < sum / 4) {
            // 전체 총합의 1/4이 아직 안 됐다면
            if (dfs(path | (1 << i), len + v[i])) {
                return true;
            }
        }
        else if (len + v[i] == sum / 4) {
            // 딱 길이가 전체 총합의 1/4이 됐다면
            // len은 다시 0으로 초기화 시켜준다.        
            if (dfs(path | (1 << i), 0)) {
                return true;
            }
        }
    }
 
    return false;
}
 
int main()
{
    cin.tie(0);
 
    int t;
    scanf("%d", &t);
    
    for (int tc = 0; tc < t; tc++) {
        memset(cache, false, sizeof(cache));
        v.clear();
        sum = 0;
 
        scanf("%d", &n);
        v.assign(n, 0);
 
        for (int i = 0; i < n; i++) {
            scanf("%d", &v[i]);
            sum += v[i];
        }
 
        if (sum % 4 != 0) {
            // 총 합이 4로 나누어 떨어지지 않는다면, 당연히 불가능하다.
            printf("no\n");
            continue;
        }
 
        printf("%s\n", dfs(0, 0) ? "yes" : "no");
    }
 
    return 0;
}