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

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

분명 이전에 풀었던 문젠데, 시간 초과가 또 떠서 당황함.  분명 로직은 별로 차이 안 나는데….
– 처음에 통과 가능한지 확인해서 가능하면 바로 통과
– 통과 불가능하면, 맨 윗줄부터 한 줄씩 ‘A로 바꿈->테스트해서 통과하면 끝/아니면 다음 줄로 넘어감->B로 바꿈->테스트해서 통과하면 끝/아니면 다음 줄로 넘어감->아무것도 안 바꿈->테스트 해서 통과하면 끝/아니면 다음 줄로 넘어감’ 하도록 구현.
– 분명 로직은 잘못되지 않았는데 시간 초과가 떠서.. 고민 좀 하다가 ‘이미 구한 최소 약품 횟수를 넘어가는 경우가 나오면 바로 종료’하는 식으로 바운드를 만들었더니 통과. 1.2초였나..? (자바 때는 3.2초 정도 걸렸음… 응!?)

#include <iostream>

using namespace std;

int minModificationNum = 13 + 1;
int map[13][20] = {{0}}; // D (row), W (column) 

void process(int numD, int numW, int numK);
void process_(int depth, int numProcessed, int numD, int numW, int numK);
bool checkPass(int numD, int numW, int numK);

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    //freopen("input.txt", "r", stdin);

    int T = 0;
    cin >> T;

    for (int test_case = 1; test_case <= T; test_case++) {
        cout << "#" << test_case << ' ';

        int numD = 0, numW = 8, numK = 3;
        cin >> numD >> numW >> numK; // K: threshold to pass

        minModificationNum = 13 + 1;

        // value 0: A, 1: B
        for (int r = 0; r < numD; r++) {
            for (int c = 0; c < numW; c++) {
                cin >> map[r];
            }
        }

        // check first it can be passed without modification
        bool passed = checkPass(numD, numW, numK);

        if (passed == true)
            cout << 0 << '\n';
        else {
            process(numD, numW, numK);
            cout << minModificationNum << '\n';
        }
    }
}

void process(int numD, int numW, int numK) {
    int backup[20] = {0};

    int theRow = 0;
    for (int i = 0; i < numW; i++)
        backup[i] = map[theRow][i];

    // first row changed to A
    for (int i = 0; i < numW; i++)
        map[theRow][i] = 0;

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > 1)
            minModificationNum = 1;

        for (int i = 0; i < numW; i++)
            map[theRow][i] = backup[i];

        return;
    }
    else 
        process_(theRow + 1, 1, numD, numW, numK);

    // first row changed to B
    for (int i = 0; i < numW; i++)
        map[theRow][i] = 1;

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > 1)
            minModificationNum = 1;

        for (int i = 0; i < numW; i++)
            map[theRow][i] = backup[i];

        return;
    }
    else 
        process_(theRow + 1, 1, numD, numW, numK);

    // first row not changed
    for (int i = 0; i < numW; i++)
        map[theRow][i] = backup[i];

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > 0)
            minModificationNum = 0;
        return;
    }
    else 
        process_(theRow + 1, 0, numD, numW, numK);
}

void process_(int depth, int numProcessed, int numD, int numW, int numK) {
    if (depth == numD)
        return;
    if (numProcessed >= minModificationNum)
        return;

    int backup[20] = {0};

    for (int i = 0; i < numW; i++)
        backup[i] = map[depth][i];

    // first row changed to A
    for (int i = 0; i < numW; i++)
        map[depth][i] = 0;
    
    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > numProcessed + 1)
            minModificationNum = numProcessed + 1;

        for (int i = 0; i < numW; i++)
            map[depth][i] = backup[i];

        return;
    }
    else
        process_(depth + 1, numProcessed + 1, numD, numW, numK);

    // first row changed to B
    for (int i = 0; i < numW; i++)
        map[depth][i] = 1;

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > numProcessed + 1)
            minModificationNum = numProcessed + 1;

        for (int i = 0; i < numW; i++)
            map[depth][i] = backup[i];

        return;
    }
    else
        process_(depth + 1, numProcessed + 1, numD, numW, numK);

    // first row not changed
    for (int i = 0; i < numW; i++)
        map[depth][i] = backup[i];

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > numProcessed)
            minModificationNum = numProcessed;

        return;
    }
    else
        process_(depth + 1, numProcessed, numD, numW, numK);
}

bool checkPass(int numD, int numW, int numK) {
    bool passed = true;
    for (int c = 0; c < numW; c++) {
        int current = map[0];
        int count = 1;

        for (int r = 1; r < numD; r++) {
            if (current == map[r]) {
                count++;
                if (count == numK) // already passed
                    break;
            }
            else {
                current = map[r];
                count = 1;
            }
        }

        if (count < numK) {
            passed = false;
            break;
        }
    }

    return passed;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.