12102번 종이 접기 2

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

브루트포스 백트래킹 dfs bitmask sw역량테스트 코딩 구현 코테 필수 추천 복습 bruteforce backtracking

이 문제는 종이를 '끝까지' 접을 필요가 없다. 

즉, 다시 말하면, 길이가 5인 종이를 위에서 아래로 3만큼 접는 것은 아래에서 위로 2만큼 접는 것과 같기 때문이다.

이외에는 모두 구현해주면 된다.

구현할 때 조심해야하는 것은 인덱스와 접었을 때 어느 행이나 열의 인덱스로 가는지이다.

참고로 dfs 함수의 인자에 num은 디버깅할 때 사용한 매개변수이니 무시해도 된다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 15
 
int n, m, p[Max][Max], ans = -1e9;
 
// 총 길이가 total이면서 len 길이를 접을 때
// 예를 들어 총 길이가 5(=total)인데 2(len)를 접으려고 하면
// 5 - 2 = 3이 된다.
// 하지만 총 길이가 5(=total)인데 3(len)을 접으려고 하면
// 5 - 3 = 2가 아니라 3이 된다.
// (물론 어차피 이 문제에서는 필요없다. 이유는 길이의 반 밖에 자르지 않으므로)
int Length(int total, int len)
{
    if (len >= (total + 1) / 2) {
        return len;
    }
    else {
        return total - len;
    }
}
 
int chk(int R, int C, int(*t)[Max])
{
    int ret = -1e9;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            ret = max(ret, t[i][j]);
        }
    }
 
    return ret;
}
 
void convert(int R, int C, int pos, int len, int(*t)[Max])
{
    int temp[Max][Max] = { 0 };
 
    // 위에서 아래로
    if (pos == 0) {
        for (int i = 2 * len; i < R; i++) {
            for (int j = 0; j < C; j++) {
                temp[i - len][j] = t[i][j];
            }
        }
    }
    // 왼쪽에서 오른쪽으로
    else if (pos == 2) {
        for (int i = 0; i < R; i++) {
            for (int j = 2 * len; j < C; j++) {
                temp[i][j - len] = t[i][j];
            }
        }
    }
 
    // 위에서 아래로
    if (pos == 0) {
        int idx = len - 1;
 
        // for문 순서 주의
        for (int u = 0, d = 2 * len - 1; u < d; u++, d--) {
            for (int j = 0; j < C; j++) {
                temp[idx][j] = t[u][j] + t[d][j];
            }
            --idx;
        }
 
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                t[i][j] = temp[i][j];
            }
        }
    }
    // 아래에서 위로
    else if (pos == 1) {
        if (R - 2 * len >= 0) {
            for (int j = 0; j < C; j++) {
                for (int u = R - 2 * len, d = R - 1; u < d; u++, d--) {
                    t[u][j] = t[u][j] + t[d][j];
                    t[d][j] = 0;
                }
            }
        }
    }
    // 왼에서 오
    else if (pos == 2) {
        int idx = len - 1;
 
        for (int l = 0, r = 2 * len - 1; l < r; l++, r--) {
 
            for (int i = 0; i < R; i++) {
                temp[i][idx] = t[i][l] + t[i][r];
 
            }
            --idx;
 
        }
 
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                t[i][j] = temp[i][j];
            }
        }
    }
    // 오에서 왼
    else if (pos == 3) {
 
        if (C - 2 * len >= 0) {
 
            for (int l = C - 2 * len, r = C - 1; l < r; l++, r--) {
 
                for (int i = 0; i < R; i++) {
                    t[i][l] = t[i][l] + t[i][r];
                    t[i][r] = 0;
                }
            }
        }
    }
}
 
void dfs(int rlen, int clen, int(*t)[Max], int num)
{
    // 각 칸들 중에서 최댓값 구하기
    ans = max(ans, chk(rlen, clen, t));
 
    int temp[Max][Max] = { 0 };
 
    // 임시 배열에 저장
    for (int i = 0; i < rlen; i++) {
        for (int j = 0; j < clen; j++) {
            temp[i][j] = t[i][j];
        }
    }
 
    // 위에서 아래로 접기 + 아래에서 위로 접기
    if (rlen > 1) {
 
        // 위에서 아래로
        for (int i = 1; i <= rlen / 2; i++) {
            if (rlen - i >= 1) {
                convert(rlen, clen, 0, i, t);
                dfs(Length(rlen, i), clen, t, num + 1);
 
                for (int a = 0; a < rlen; a++) {
                    for (int b = 0; b < clen; b++) {
                        t[a][b] = temp[a][b];
                    }
                }
            }
        }
 
        // 아래에서 위로
        for (int i = 1; i <= rlen / 2; i++) {
            if (rlen - i >= 1) {
                convert(rlen, clen, 1, i, t);
                dfs(Length(rlen, i), clen, t, num + 1);
 
                for (int a = 0; a < rlen; a++) {
                    for (int b = 0; b < clen; b++) {
                        t[a][b] = temp[a][b];
                    }
                }
            }
        }
    }
 
    // 왼쪽에서 오른쪽으로 접기 + 오른쪽에서 왼쪽으로 접기
    if (clen > 1) {
 
        // 왼에서 오
        for (int i = 1; i <= clen / 2; i++) {
            if (clen - i >= 1) {
                convert(rlen, clen, 2, i, t);
                dfs(rlen, Length(clen, i), t, num + 1);
 
                for (int a = 0; a < rlen; a++) {
                    for (int b = 0; b < clen; b++) {
                        t[a][b] = temp[a][b];
                    }
                }
            }
        }
 
        // 오에서 왼
        for (int i = 1; i <= clen / 2; i++) {
            if (clen - i >= 1) {
                convert(rlen, clen, 3, i, t);
                dfs(rlen, Length(clen, i), t, num + 1);
 
                for (int a = 0; a < rlen; a++) {
                    for (int b = 0; b < clen; b++) {
                        t[a][b] = temp[a][b];
                    }
                }
            }
        }
    }
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\input.txt", "r", stdin);
    cin.tie(0);
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &p[i][j]);
        }
    }
 
    if (n == 1 && m == 1) {
        printf("%d\n", p[0][0]);
    }
    else {
        dfs(n, m, p, 1);
 
        printf("%d\n", ans);
    }
 
    return 0;
}