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

 

출처 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

 

역대급 레전드 문제....

구현도 구현인데 그보다 시간줄이기가 가장 힘들었다.

 

DFS에서 가장 핵심은 재귀하면서 재귀로 또 나아가지 않아도 될 조건들을 찾아서 해당 조건에서 진행을 무시하도록 하는 것인데 ,,, 여러 아이디어가 있다.

검사 함수를 하드코딩으로 하는 것, 그리고 필요없는 count에 대한 무시, 검사시에 끝까지 진행하기 전에 탈출 하기. 등등

 

그리고 DFS에서 나는 카운트를 인자로 넘겨서 그 카운트부터 인덱스가 진행되게 했는데 같은 카운트에 대해 다른 인덱스가 존재 할 수 있고 이를 통해 더 빨리 결과값을 찾아 낼 수 있기 때문에 고쳤다.

 

 

#include <iostream>



using namespace std;

int tc,D,W,K;
int result;
int m;
int arr[13+1][20+1];



bool check()
{

int count ,current ;
int num = 0;
bool che = false;


    for(int i = 1; i <= W; i++)
{
current = -1;
count = 1;

for(int j = 1; j<=D; j++)
{
if(current != arr[j][i])
{
count = 1;
current =arr[j][i];
}
else{


count++;
}


if(count == K)
break;



if(j == D)
{
che = true;
break;
}



}


if(che)
break;

if(count == K)
{

num++;

}

   }














    
    if(num == W)
    return true;
    
    else{
     return false;
}


}




void DFS(int count, int index)
{

    if(count >= result || count > K )
    return;


if(check() )
{


result = count;
return;
}





int temp[21];




for(int i = index+1; i <=D; i++)
{

for(int j = 1; j <= W; j++)
{
temp[j] = arr[i][j];
}

//


for(int j = 1; j <= W; j++)
{
arr[i][j] = 0;
}



DFS(count+1,i);



//


for(int j = 1; j <= W; j++)
{
arr[i][j] = 1;

}

DFS(count+1,i);


for(int j = 1; j <= W; j++)
{
arr[i][j] = temp[j];

}

    

    
    
    
}



}





int main(void)
{



cin >> tc;



for(int i = 1; i<=tc; i++)
{


    
    result = 987654321;
    
cin>>D>>W>>K;



for(int y = 1; y <= D; y++)
    {
for(int x = 1; x <= W; x++)
{
cin >> arr[y][x];

}

    }
    
    
if(K == 1)
{
 cout<<"#"<<i<<" "<<0<<endl;
}
else{


      DFS(0,0);
      
      cout<<"#"<<i<<" "<<result<<endl;


}














}




}