[SW Expert Academy] 2112. [모의 SW 역량테스트] 보호 필름 풀이 (C++)

2017. 10. 18에 쓰여진 글입니다.

---

문제링크

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

SW Expert Academy

 

풀이방법

1. 비트마스크 이용 (부분집합 이용하기)

약품처리를 해줄 행을 

1행

2행

1행 2행

3행

...

이런식으로 비트를 이용해서 하기때문에 플래그가 저렇게 되서 결국 완전 탐색을 해야함

이때 만약 통과가 되는 것이 있다면 그때의 행갯수를 저장해놓고 그거보다 크면 굳이 확인을안해보는 식이었음. 그래서 시간은 0.01초때가 나옴.

 

2. 재귀로 그냥 짜기

약품처리를 해줄 행을

1행

2행

3행

4행

5행

6행

1행 2행

1행 3행

1행 4행

...

이런식으로 하기때문에 찾으면 바로 그 테케를 끝냄. 그래서 속도가 빠름. (0.003초)

 

※혹시 48개 또는 49개에서 시간초과나신다면 보호필름 성능검사하는 함수를 다시 보시길 바랍니다.

check함수를 잘못짠건줄 모르고 48개 맞고 계속 시간초과로 틀려서 엄청 고생했...... 

 

​-2018.04.02 추가

다시 풀어봤는데 아무생각없이 부분집합을 이용해서 풀었고 또 다시 시간초과..

아니 전에도 check함수가 문제였는데 이번도 ㅋㅋㅋ 하나의 오차도 없이 내가 시간초과났던 코드 그대로 작성되어있어서 놀람 -_-;; 

나는 발전이 없는것인가.. 흑흑

문제가 뭐냐면 

시간초과나는건 모든열을 검사해줬고,

시간초과가 안나는건 검사하다가 만약에 기준을 통과못하면 그냥 다른열검사안하고 통과못했다고 false리턴

크게 차이없을거라고 생각했는데 차이가 있어서 또다시 놀람.

 

시간초과 나는 check 함수 소스코드

bool check()        //통과기준체크 함수
{
    int pass_cnt = 0;
    for (int j = 0; j < W; j++) {
        int cnt = 1;
        int cur_cell = map[0][j];
        for (int i = 1; i < D; i++) {
            if (map[i][j] == cur_cell)
                cnt++;
            else {
                cur_cell = map[i][j];
                cnt = 1;
            }
            if (cnt == K) {
                pass_cnt++;
                break;
            }
        }
    }
    if (pass_cnt == W)
        return true;
    return false;
}   //통과기준체크

 

시간초과 안나는 check함수 소스코드

bool check()        //통과기준체크 함수
{
    bool flag;
    for (int j = 0; j < W; j++) {        //모든 열을 다체크함
        flag = false;                    //flag는 false로 초기화
        int cnt = 1;                    //카운트는 1
        int cur_cell = map[0][j];        //해당 열의 제일 첫번째 행값을 저장
        for (int i = 1; i < D; i++) {    //그다음행부터 돌꺼임
            if (map[i][j] == cur_cell)    //같으면 
                cnt++;                    //카운트증가
            else {
                cur_cell = map[i][j];    //다르면 다른거 넣어주고
                cnt = 1;                //카운트 1로 초기화
            }
            if (cnt == K) {                //통과기준 K와 같아지면
                flag = true;            //flag를 true로 해줌 
                break;                    //탈출
            }
        }
        if (!flag)                        //다돌았는데 flag가 false면
            return false;                //해당 열이 기준을 통과못함. 따라서 false리턴
    }
    return true;                        //다돌면 통과기준이 true인것임
}

 

재귀 버전으로도 풀었었네.. 저걸로도 한번 다시 풀어봐야겟다.. 

왜 예전의 내가 코딩을 더 잘하는것같은 이상한 느낌이 요새 마구드는지 흑흑ㅠㅠ

재귀로도 다시 풀어봄.

계속 시간 초과 나길래 뭐가 문제지했는데 문제를 발견함

 

이번에는 dfs함수가 문제였음.

void dfs(int cnt,int end_cnt,int cur_x)
{
    if (cnt == end_cnt) {                    //둘이 같아지면
        if (check()) {                        //check해보고
            Answer = min(Answer, end_cnt);    //통과되면 정답 최소값 저장
            flag = true;                    //flag를 true로~
        }
        return;                                //리턴시킴
    }
    for (int i = cur_x; i < D; i++) {        //현재 행부터 돌림(1,2를 체크하고나면 2,1을 굳이 체크안해주기 위함)
        if (flag)
            return;                            //되면 굳이 계속돌려볼필요가없음
        if (!use_col[i]) {
            use_col[i] = true;                //지금 행썼다고 표시
            for (int j = A; j <= B; j++) {    //AB돌리기
                if (flag)
                    return;                    //되면 굳이 계속 돌려볼필요가없음
                drug(i, j);                    //약품처리해줌
                dfs(cnt + 1, end_cnt, i);    //재귀로 들어감
            }
            restore_col(i);                    //해당행복구
            use_col[i] = false;                //해당행 안썼다고 다시 표시해줌
        }
    }
}

이부분에서 for문을 돌리는 저부분.

i 를 기존에는 0부터 시작해줬음. 그래서 시간초과가 남.

이유는

1행 2행 을 하고선

2행 1행을 또 처리해줌. 그러니까 시간이 배로듬

그래서 시작을 cur_x 로 잡아주니

1행 2행후 

2행을 돌때는 

2행 3행 부터 시작하게됨

이런식으로 시간을 대폭줄여주니 통과. (이전에는 35개만맞다고나오고 시간초과)

부분집합이용도 좋지만 재귀를 이용한 것도 자꾸 풀어봐야겠다. 내 재귀스킬이 자꾸 구려지는 중이라 다시 빡공해야겠음..

숫자만들기 문제도 재귀로 풀때는 시간초과가 난 이유는 이것때문인거같음.

무튼 보호필름문제 굉장히 흥미롭고 좋은 문제라고 생각. 배운것이 많음.

여러풀이방법으로 도전해볼가치가 있는 좋은 문제.

 

소스코드

소스코드1 (비트마스크, 부분 집합 이용)

#include <iostream>
#include <vector>        //벡터
#include <algorithm>    //min max 위한 헤더
 
using namespace std;
 
enum { BLANK = -1, A = 0, B = 1 };
 
int D, W, K;            //두께, 가로길이, 합격기준
int map[13][20];        //맵
int tmp_map[13][20];    //임시맵
int Answer;                //정답
vector < int > v;        //부분집합 저장할 배열
 
void Init()            //초기화
{
    for (int i = 0; i < D; i++)
        for (int j = 0; j < W; j++)
            map[i][j] = BLANK;
}
 
void copy_map_tmp()        //map을 tmp로 복사
{
    for (int i = 0; i < D; i++)
        for (int j = 0; j < W; j++)
            tmp_map[i][j] = map[i][j];
}
 
void copy_tmp_map()        //tmp를 맵으로 복사
{
    for (int i = 0; i < D; i++)
        for (int j = 0; j < W; j++)
            map[i][j] = tmp_map[i][j];
}
 
void drug(int col, int cell)    //약품투여
{
    for (int i = 0; i < W; i++)
        map[col][i] = cell;
}
 
bool check()        //통과기준체크 함수
{
    bool flag;
    for (int j = 0; j < W; j++) {        //모든 열을 다체크함
        flag = false;                    //flag는 false로 초기화
        int cnt = 1;                    //카운트는 1
        int cur_cell = map[0][j];        //해당 열의 제일 첫번째 행값을 저장
        for (int i = 1; i < D; i++) {    //그다음행부터 돌꺼임
            if (map[i][j] == cur_cell)    //같으면 
                cnt++;                    //카운트증가
            else {
                cur_cell = map[i][j];    //다르면 다른거 넣어주고
                cnt = 1;                //카운트 1로 초기화
            }
            if (cnt == K) {                //통과기준 K와 같아지면
                flag = true;            //flag를 true로 해줌 
                break;                    //탈출
            }
        }
        if (!flag)                        //다돌았는데 flag가 false면
            return false;                //해당 열이 기준을 통과못함. 따라서 false리턴
    }
    return true;                        //다돌면 통과기준이 true인것임
}
 
void dfs(int cnt)
{
    if (cnt == v.size()) {                //카운트가 현재 벡터 갯수랑 같아지면
        if (check())                    //통과기준 검사
            Answer = min(cnt, Answer);    //정답저장
        return;
    }
    for (int i = A; i <= B; i++) {        //A B 돌리기
        drug(v[cnt], i);                //약품처리해줌
        dfs(cnt + 1);                    //재귀로 들어감
    }
}
 
void solve()
{
    for (int i = 1; i < (1 << D); i++) {    //부분집합 돌리기
        v.clear();                            //벡터비워주고
        copy_tmp_map();                        //tmp에 있는걸 맵으로 복사호줌
        for (int j = 0; j < D; j++) {        //모든행 돌리기
            if (i&(1 << j))                    //부분집합 구해줌
                v.push_back(j);                //벡터에저장
        }
        if (v.size() < Answer)                //정답보다 벡터 사이즈가 작으면(크면 패스)
            dfs(0);                            //그때 돌려봄
    }
}
 
int main()
{
    //freopen("sample_input.txt", "r", stdin);
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; test_case++) {
        Answer = 987654321;                //정답초기화
        cin >> D >> W >> K;                //입력받기
        Init();                            //초기화
        for (int i = 0; i < D; i++)
            for (int j = 0; j < W; j++)
                cin >> map[i][j];
        copy_map_tmp();                    //맵 임시 복사해놈
        if (!check())                    //약품투어안해도 통과하는지 체크
            solve();
        else
            Answer = 0;
        cout << "#" << test_case << " " << Answer << endl;
    }
 
    return 0;
}

 

소스코드2 (재귀로 그냥 짜기)

#include <iostream>
#include <vector>        //벡터
#include <algorithm>    //min max 위한 헤더
 
using namespace std;
 
enum { BLANK = -1, A = 0, B = 1 };
 
int D, W, K;            //두께, 가로길이, 합격기준
int map[13][20];        //맵
int tmp_map[13][20];    //임시맵
int drug_map[13][20];    //임시맵
bool use_col[13];        //해당 행 썼는지 체크
int Answer;                //정답
bool flag;
 
void Init()            //초기화
{
    for (int i = 0; i < D; i++)
        for (int j = 0; j < W; j++)
            map[i][j] = BLANK;
    for (int i = 0; i < D; i++)
        use_col[i] = false;
}
 
void copy_map_tmp()        //map을 tmp로 복사
{
    for (int i = 0; i < D; i++)
        for (int j = 0; j < W; j++)
            tmp_map[i][j] = map[i][j];
}
 
void copy_tmp_map()        //tmp를 맵으로 복사
{
    for (int i = 0; i < D; i++)
        for (int j = 0; j < W; j++)
            map[i][j] = tmp_map[i][j];
}
 
void restore_col(int col)        //해당행복구
{
    for (int j = 0; j < W; j++)
        map[col][j] = tmp_map[col][j];
}
 
void drug(int col, int cell)    //약품투여
{
    for (int i = 0; i < W; i++)
        map[col][i] = cell;
}
 
bool check()        //통과기준체크 함수
{
    bool flag;
    for (int j = 0; j < W; j++) {        //모든 열을 다체크함
        flag = false;                    //flag는 false로 초기화
        int cnt = 1;                    //카운트는 1
        int cur_cell = map[0][j];        //해당 열의 제일 첫번째 행값을 저장
        for (int i = 1; i < D; i++) {    //그다음행부터 돌꺼임
            if (map[i][j] == cur_cell)    //같으면 
                cnt++;                    //카운트증가
            else {
                cur_cell = map[i][j];    //다르면 다른거 넣어주고
                cnt = 1;                //카운트 1로 초기화
            }
            if (cnt == K) {                //통과기준 K와 같아지면
                flag = true;            //flag를 true로 해줌 
                break;                    //탈출
            }
        }
        if (!flag)                        //다돌았는데 flag가 false면
            return false;                //해당 열이 기준을 통과못함. 따라서 false리턴
    }
    return true;                        //다돌면 통과기준이 true인것임
}
 
void dfs(int cnt,int end_cnt,int cur_x)
{
    if (cnt == end_cnt) {                    //둘이 같아지면
        if (check()) {                        //check해보고
            Answer = min(Answer, end_cnt);    //통과되면 정답 최소값 저장
            flag = true;                    //flag를 true로~
        }
        return;                                //리턴시킴
    }
    for (int i = cur_x; i < D; i++) {        //현재 행부터 돌림(1,2를 체크하고나면 2,1을 굳이 체크안해주기 위함)
        if (flag)
            return;                            //되면 굳이 계속돌려볼필요가없음
        if (!use_col[i]) {
            use_col[i] = true;                //지금 행썼다고 표시
            for (int j = A; j <= B; j++) {    //AB돌리기
                if (flag)
                    return;                    //되면 굳이 계속 돌려볼필요가없음
                drug(i, j);                    //약품처리해줌
                dfs(cnt + 1, end_cnt, i);    //재귀로 들어감
            }
            restore_col(i);                    //해당행복구
            use_col[i] = false;                //해당행 안썼다고 다시 표시해줌
        }
    }
}
 
void solve()
{
    flag = false;                //flag는 false로 초기화
    int end_cnt = 1;            //end_cnt는 1로 초기화
    while (!flag) {                //flag가 true가 될때까지
        dfs(0, end_cnt, 0);        //시작카운트0,end_cnt,시작행 0
        end_cnt++;                //end_cnt증가
    }
}
 
int main()
{
    //freopen("sample_input.txt", "r", stdin);
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; test_case++) {
        Answer = 987654321;                //정답초기화
        cin >> D >> W >> K;                //입력받기
        Init();                            //초기화
        for (int i = 0; i < D; i++)
            for (int j = 0; j < W; j++)
                cin >> map[i][j];
        copy_map_tmp();                    //맵 임시 복사해놈
        if (!check())                    //약품투어안해도 통과하는지 체크
            solve();
        else
            Answer = 0;
        cout << "#" << test_case << " " << Answer << endl;
    }
 
    return 0;
}