BOJ 14391

종이 조각

문제출처

문제 해석

  • NxN크기의 종이를 가로 또는 세로로 잘라서 각 조각의 숫자의 합이 최대가 되게 하는 문제입니다.

설계(10)

  • 아주작은 범위를 다루므로(N<=4) 완전탐색으로 풀이가 가능합니다.
  • 비트마스크를 이용하여 가로 또는 세로로 지정해준 다음 더해주는 방법이 있습니다.
  • 다른 방법으로는 백트래킹기법으로 모든 가로 또는 세로 조각을 더하는 방법이 있습니다.
  • 저는 백트래킹 기법을 사용하고자 하였습니다.
  • 완벽하게 구현을 하지 못해서 kks227님의 코드를 참조하였습니다.
  • 제가 한 구현과 달랐던 점은 체크하지 않은 좌표를 찾은 후, 해당 좌표를 기준으로 가로와 세로 조각을 만들도록 구현하는 것이었습니다.
  • 저같은 경우에는, 모든 좌표를 돌면서 세로와 가로조각을 만들도록 했으나 재귀적 특성상 기저사례를 마땅하게 지정을 할 수 없었습니다.

구현(X)

코드
#include <iostream>
using namespace std;
#define MAXN 4

int map[MAXN][MAXN];
bool visited[MAXN][MAXN];
int N, M;
int ans;

pair<int,int> find_coord(){
    for (int x = 0; x < N; x++){
        for (int y = 0 ;y <M; y++){
            if (!visited[x][y]){
                return {x,y};
            }
        }
    }
    return {-1,-1};
}
void dfs(int sum){

    pair<int,int> coord = find_coord();
    int x = coord.first;
    int y = coord.second;
    if (coord.first == -1){
        if (ans < sum) ans = sum;
        return;
    }
    int tmp = 0;
    int len = 0;
    for (int i= 0; i + x < N && !visited[i+x][y]; i++){
        visited[i+x][y] = true;
        tmp *= 10;
        tmp += map[i+x][y];
        len++;
        dfs(sum+tmp);

    }
    for (int i = 1; i <len; i++){
        visited[i+x][y] = false;
    }
    len = 1;
    tmp = map[x][y];
    for (int i = 1; i + y <M && !visited[x][i+y]; i++){
        visited[x][i+y] = true;
        tmp *= 10;
        tmp += map[x][i+y];
        len++;
        dfs(sum+tmp);
    }
    for (int i = 0; i < len; i++){
        visited[x][i+y] = false;
    }
}
int main(){
    scanf("%d%d",&N,&M);
    for (int i = 0; i < N; i++){
        for (int j = 0;j<M;j ++){
            scanf("%1d",&map[i][j]);
        }
    }
    dfs(0);
    cout << ans <<"\n";
    return 0;
}
디버깅
제출결과
  • 4ms

마무리

  • 비트마스킹같은 쉬운방법이 있었지만, 취약점으로 생각하는 백트래킹 기법을 숙련시키고자 해당 방법으로 구현을 시도하였습니다.
  • 재귀적특성을 제대로 이해하지 못한 탓인지, 이와 같은 문제는 여태껏 풀기가 어려웠습니다.(색종이 붙이기와 같은 문제도 마찬가지입니다.)
  • 비슷한 유형의 문제를 여러번 풀어서 숙련시키는 연습을 해야 할 것 같습니다.