2112. [모의 SW 역량테스트] 보호 필름

정답률에 비해 금방 푼 문제. 1시간 30분 컷.

최근 정답률은 무의미 하다는게 느껴진다. 이건 그냥 백트랙킹 문제인데 조건이 만 좀 잘 따져주면 된다. 지금 내 상태에서도 조건 잘 따져주면 시간 줄일 수 있겟지만 모르겠다!!!

접근법

1. 두께 d에서 A 또는 B로 바꾸는 조합을 구해 바꾸어준다.

2. D에서 K개 만큼 연속된 필름이 있는지 판단.

3. K개만큼 W가 전부 만족하면 MIN값 판단 후, 갱신.

끝.

#include <stdio.h>
#include <string.h>
 
void Init();
void Input();
int Check(int arr[15][25]);
int map[15][25], D, W, K, MIN;
int visit[15];
 
void DFS(int cur, int n, int M[15][25])
{
    if (n > K || n >= MIN)
        return;
 
    if (Check(M))
    {
        if (n < MIN)
            MIN = n;
        return;
    }
 
    int copy[25] = { 0, };
 
    for (int i = cur + 1; i <= D; i++)
    {
        for (int j = 0; j <= 1; j++)
        {
            for (int w = 1; w <= W; w++)
                copy[w] = M[i][w];
 
            for (int w = 1; w <= W; w++)
                M[i][w] = j;
 
            DFS(i, n + 1, M);
 
            for (int w = 1; w <= W; w++)
                M[i][w] = copy[w];
        }
    }
 
    return;
}
 
int main()
{
    int Test_Case;
    scanf("%d", &Test_Case);
 
    for (int T = 1; T <= Test_Case; T++)
    {
        Init();
        Input();
 
        DFS(0, 0, map);
 
        printf("#%d %d\n", T, MIN);
    }
 
    return 0;
}
 
int Check(int arr[15][25])
{
    int Flag1 = 1, Flag2 = 1;
    for (int w = 1; w <= W; w++)
    {
        Flag2 = 1;
        for (int d = 1; d <= D; d++)
        {
            Flag1 = 1;
            for (int i = 0; i < K; i++)
            {
                if (arr[d][w] != arr[d + i][w])
                {
                    Flag1 = 0;
                    break;
                }
            }
            if (Flag1)
            {
                Flag2 = 0;
                break;
            }
        }
        if (Flag2)
            return 0;
    }
    return 1;
}
 
void Init()
{
    memset(map, -1, sizeof(map));
    memset(visit, 0, sizeof(visit));
    D = W = K = 0;
    MIN = 987654321;
}
 
void Input()
{
    scanf("%d %d %d", &D, &W, &K);
    for (int d = 1; d <= D; d++)
    {
        for (int w = 1; w <= W; w++)
        {
            scanf("%d", &map[d][w]);
        }
    }
}