[SWEA] 보호필름

[문제]

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

SW Expert Academy

[풀이]

제출일 : 2019-08-01 13:42

• C++언어
• 12,628 kb메모리
• 3,948 ms실행시간
• 1,846코드길이
• Pass결과

1) 입력 : 세로 D, 가로 W, 통과 기준 K

 

2) 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.

 

3) 셀을 구성하는 특징은 A, B 두 가지이다. (A : 0 / B : 1) 

 

3) 약품을 투입하면 한 행의 모든 셀이 같은 특성으로 변경된다. 

 

4) 구하는 값 : 성능검사를 통과하기 위한 최소 약품투입 횟수

 

5) 약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.

• k == 1 인 경우 

• 입력 값이 이미 k를 만족하는 경우

6) 처음 입력값을 보존하고 복사한 맵에 약품을 주입한 후 다시 되돌리는 과정이 중요하다.

 

7) dfs(cur : 현재 검사하는 행,  cnt : 약품 투입 횟수)

 

8) 댓글에서 얻은 팁인데, d행 중 k개의 연속적인 특성을 만족함 -> d-k+1 까지 검사했을 때 연속된 특성이 K개가 아닐 경우에는 그 열은 통과되지 못한다. => 다음 열을 검사한다. 

 

9)  현재 검사하는 행이 d와 같더라도 (끝까지 검사) 바로 리턴하지 않고 검사 조건(k)를 만족했는지 확인하고 최소값을 갱신한다. 

(여기서 계속 바로 리턴을 해줘서 테스트케이스를 통과하지 못했다..)

 

10) 팁이라면 팁인데, 입력받은 맵과 그 맵을 복사한 값을 전역변수로 두고 복사맵을 변경한 후 되돌리는 값으로 원래 맵을 사용한다. 

(재귀 함수에 계속 map을 넘기다 보면 결국 map이 변경돼서 몇몇 테스트 케이스를 통과하지 못한다.)

 

* isThereK() => 한 열에 k 개의 특성이 연속되어 나타나는지 확인 

 

---

 

#include <iostream>
#include <cstring>
#include <climits>
 
#define INF 10000
using namespace std;
 
int d, w, k;
int ans;
bool c_film[13][20], film[13][20];
 
bool isThereK()
{
    //k개의 특성이 연속되는지 확인
    bool flag = false;
    for (int j = 0; j < w; j++)
    {
        for (int i = 0; i < d - k + 1; i++) //d-k+1까지만 살펴봐도 연속된 특성이 없으면 그 열은 검사에 통과하지 못한다.
        {
            for (int z = 1; z < k; z++)
            {
                if (c_film[i][j] != c_film[i + z][j])
                {
                    flag = false;
                    break;
                }
                else
                    flag = true;
            }
            if (flag)
                break; //이미 검사 완료
        }               //for d
        if (!flag)
            return false; //하나의 열이라도 만족하지 못하면 검사 종료
    }                      //for w
    return true;
}
 
void dfs(int cur, int cnt)
{
    if (cur == d)
    { //마지막 행이 바뀌면 통과 될 수도 있기 때문에 바로 리턴하지 않고 값을 갱신해준다. 
    
        if (isThereK())
        {
            if (ans > cnt)
            {
                ans = cnt;
            }
        }
    }
 
    else
    {
        //dfs 호출
        dfs(cur + 1, cnt);
 
        //약물 넣는 과정
        memset(c_film[cur], false, w);
        dfs(cur + 1, cnt + 1);
        memset(c_film[cur], true, w);
        dfs(cur + 1, cnt + 1);
 
        //약물 넣기 전으로 되돌리기
        memcpy(c_film[cur], film[cur], w);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin >> t;
 
    for (int tc = 1; tc <= t; tc++)
    {
 
        cin >> d >> w >> k; //세로 /가로 /테스트 통과 조건
 
        memset(c_film, false, sizeof(c_film));
        memset(film, false, sizeof(film));
        for (int i = 0; i < d; i++)
        {
            for (int j = 0; j < w; j++)
            {
                cin >> c_film[i][j]; // a = 0 / b = 1;
                film[i][j] = c_film[i][j];
            }
        }
        //입력
 
        if (k == 1)
        {
            //통과 기준이 1이면 입력 값이 정답이다.
            cout << "#" << tc << " " << 0 << '\n';
            continue;
        }
        if (!isThereK())
        {
            ans = INT_MAX;
 
            dfs(0, 0);
        }
        else
        {
            ans = 0;
        }
        //성능검사
 
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}