18430번 무기 공학

https://www.acmicpc.net/problem/18430

 

저번 풀이 : https://hsdevelopment.tistory.com/507

18430번 무기 공학

 

오랜만에 다시 풀어보았는데, 5%에서 계속 틀렸다.

 

오답 소스코드가 틀린 이유는 크게 2가지다.

 

1. simulation() 함수 내에서 for(k:0~4)만 해줘도 되는데, 삼중 for문(for i:0~n, j:0~m, k:0~4)을 활용하고 있었다. 

2. 만약 삼중 for문이 수행되지 않았다면, 현재 좌표(r, c)에서 다음 좌표(r, c+1)로 넘어간다.

 

이유는

 

2. 현재 좌표(r, c)를 부메랑으로 사용할지 말지 2가지의 경우를 모두 고려해야한다.

오답인 소스코드는 현재 좌표(r, c)를 부메랑으로 사용한 후에는 go bool 변수에 true로 표시하는 바람에 그 밑의 경우(현재 좌표를 부메랑으로 사용하지 않을 때)가 수행되지 않는다. 그래서, 단순 go bool 변수를 사용하지 않고, 삼중 for문 밑에 바로 simulation(r, c+1);만 두면, 1번 때문에 바로 시간 초과가 발생한다.

 

1. 그리고, simulation() 함수 내에서 삼중 for문을 활용할 필요가 없다. 어차피 단순 for(k:0~4)만 있어도, 각각의 좌표에 대해서, 모든 경우의 수(k:0~4 and 부메랑 사용여부)를 고려할 수 있다. 즉, 삼중 for문을 그대로 두면, 중복되는 좌표 즉, 중복되는 좌표를 호출하는 simulation 함수가 많아진다.

 

오답

#include <bits/stdc++.h>

using namespace std;

#define MAX 7

int n, m, ans;
int board[MAX][MAX];
int score[MAX][MAX];
bool used[MAX][MAX];

void visit(int r, int c, int k, bool b) {
    if (k == 0) {
        used[r + 1][c + 1] = b;
        used[r][c]         = b;
        used[r][c + 1]     = b;

        score[r + 1][c + 1] = b ?     board[r + 1][c + 1] : 0;
        score[r][c]         = b ?     board[r]    [c]     : 0;
        score[r][c + 1]     = b ? 2 * board[r]    [c + 1] : 0;
    }
    else if (k == 1) {
        used[r + 1][c + 1] = b;
        used[r + 1][c]     = b;
        used[r][c + 1]     = b;

        score[r + 1][c + 1] = b ? 2 * board[r + 1][c + 1] : 0;
        score[r + 1][c]     = b ?     board[r + 1][c]     : 0;
        score[r][c + 1]     = b ?     board[r]    [c + 1] : 0;
    }
    else if (k == 2) {
        used[r + 1][c + 1] = b;
        used[r + 1][c]     = b;
        used[r][c]         = b;

        score[r + 1][c + 1] = b ?     board[r + 1][c + 1] : 0;
        score[r + 1][c]     = b ? 2 * board[r + 1][c]     : 0;
        score[r][c]         = b ?     board[r]    [c]     : 0;
    }
    else if (k == 3) {
        used[r][c + 1] = b;
        used[r + 1][c] = b;
        used[r][c]     = b;

        score[r][c + 1] = b ?     board[r]    [c + 1] : 0;
        score[r + 1][c] = b ?     board[r + 1][c]     : 0;
        score[r][c]     = b ? 2 * board[r]    [c]     : 0;
    }
}

//           n(세로)m(가로)
bool chk(int r, int c, int k) {

    if (k == 0) {
        return r + 1 < n && c + 1 < m && !used[r + 1][c + 1] && !used[r][c] && !used[r][c + 1];
    }
    else if (k == 1) {
        return r + 1 < n && c + 1 < m && !used[r + 1][c + 1] && !used[r + 1][c] && !used[r][c + 1];
    }
    else if (k == 2) {
        return r + 1 < n && c + 1 < m && !used[r + 1][c + 1] && !used[r + 1][c] && !used[r][c];
    }
    else if (k == 3) {
        return r + 1 < n && c + 1 < m && !used[r][c + 1] && !used[r + 1][c] && !used[r][c];
    }

    return false;
}

void draw() {
    printf("\n■■■■■■■■■■■■■■■■■■■■■■■■\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            printf("%2d ", score[i][j]);
        }
        printf("\n");
    }
}

int sum() {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ret += score[i][j];
        }
    }
    return ret;
}

//                  n(세로)m(가로)
void simulation(int r, int c) {
    if (c == m) {
        c = 0;
        ++r;
    }

    if (r == n) {
        //draw();
        ans = max(ans, sum());
        return;
    }

    bool go = false;

    for (int i = r; i < n; i++) {
        for (int j = c; j < m; j++) {
            for (int k = 0; k < 4; k++) {
                if (chk(i, j, k)) {
                    visit(i, j, k, true);
                    go = true;
                    simulation(i, j + 1);
                    visit(i, j, k, false);
                }
            }
        }
    }

    if (!go) {
        simulation(r, c + 1);
    }
}

int main()
{
    cin.tie(0);

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &board[i][j]);
        }
    }

    simulation(0, 0);

    printf("%d\n", ans);

    return 0;
}

 

 

 

정답

#include <bits/stdc++.h>

using namespace std;

#define MAX 7

int n, m, ans;
int board[MAX][MAX];
int score[MAX][MAX];
bool used[MAX][MAX];

void visit(int r, int c, int k, bool b) {
    if (k == 0) {
        used[r + 1][c + 1] = b;
        used[r][c]         = b;
        used[r][c + 1]     = b;

        score[r + 1][c + 1] = b ?     board[r + 1][c + 1] : 0;
        score[r][c]         = b ?     board[r]    [c]     : 0;
        score[r][c + 1]     = b ? 2 * board[r]    [c + 1] : 0;
    }
    else if (k == 1) {
        used[r + 1][c + 1] = b;
        used[r + 1][c]     = b;
        used[r][c + 1]     = b;

        score[r + 1][c + 1] = b ? 2 * board[r + 1][c + 1] : 0;
        score[r + 1][c]     = b ?     board[r + 1][c]     : 0;
        score[r][c + 1]     = b ?     board[r]    [c + 1] : 0;
    }
    else if (k == 2) {
        used[r + 1][c + 1] = b;
        used[r + 1][c]     = b;
        used[r][c]         = b;

        score[r + 1][c + 1] = b ?     board[r + 1][c + 1] : 0;
        score[r + 1][c]     = b ? 2 * board[r + 1][c]     : 0;
        score[r][c]         = b ?     board[r]    [c]     : 0;
    }
    else if (k == 3) {
        used[r][c + 1] = b;
        used[r + 1][c] = b;
        used[r][c]     = b;

        score[r][c + 1] = b ?     board[r]    [c + 1] : 0;
        score[r + 1][c] = b ?     board[r + 1][c]     : 0;
        score[r][c]     = b ? 2 * board[r]    [c]     : 0;
    }
}

//           n(세로)m(가로)
bool chk(int r, int c, int k) {
    if (k == 0) {
        return r + 1 < n && c + 1 < m && !used[r + 1][c + 1] && !used[r    ][c] && !used[r][c + 1];
    }
    else if (k == 1) {
        return r + 1 < n && c + 1 < m && !used[r + 1][c + 1] && !used[r + 1][c] && !used[r][c + 1];
    }
    else if (k == 2) {
        return r + 1 < n && c + 1 < m && !used[r + 1][c + 1] && !used[r + 1][c] && !used[r][c    ];
    }
    else if (k == 3) {
        return r + 1 < n && c + 1 < m && !used[r    ][c + 1] && !used[r + 1][c] && !used[r][c    ];
    }
}

void draw() {
    printf("\n■■■■■■■■■■■■■■■■■■■■■■■■\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            printf("%2d ", score[i][j]);
        }
        printf("\n");
    }
}

int sum() {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ret += score[i][j];
        }
    }
    return ret;
}

//                  n(세로)m(가로)
void simulation(int r, int c) {
    if (c == m) {
        c = 0;
        ++r;
    }

    if (r == n) {
        //draw();
        ans = max(ans, sum());
        return;
    }

    bool go = false;

    for (int k = 0; k < 4; k++) {
        if (chk(r, c, k)) {
            visit(r, c, k, true);
            go = true;
            simulation(r, c + 1);
            visit(r, c, k, false);
        }
    }

    simulation(r, c + 1);
}

int main()
{
    cin.tie(0);

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &board[i][j]);
        }
    }

    simulation(0, 0);

    printf("%d\n", ans);

    return 0;
}