BOJ 14391 종이조각

 

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

14391번: 종이 조각

 

완전탐색 문제이다.

(r,c) 에서 오른쪽으로 한칸씩 늘리거나. 아래쪽으로 한칸씩 늘려 종이 조각의 숫자를 구하고, 이를 재귀적으로 완전탐색하여 풀면 된다.

내 코드는 다음과 같다.

#include <cstdio>

int n,m;
int map[4][4];
int answer = 0;

bool checked[4][4];

void dfs(int r, int c, int max){

    if(c >= m){ c = 0; ++r; }
    if(r >= n){
        //printf("temp answer : %d\n", max);
        if(max > answer) answer = max;
        return;
    }
    if(checked[r][c]){
        dfs(r,c+1, max);
        return;
    }

    int t = 0;
    for(int i=0;c+i<m;i++){
        if(checked[r][c+i]) break;
        for(int j=0;j<=i;j++)
            checked[r][c+j] = true;
        t *= 10;
        t += map[r][c+i];

        dfs(r,c+1, max+t);
        for(int j=0;j<=i;j++)
            checked[r][c+j] = false;
    }

    t = 0;
    for(int i=0;r+i<n;i++){
        if(checked[r+i][c]) break;
        for(int j=0;j<=i;j++)
            checked[r+j][c] = true;
        t *= 10;
        t += map[r+i][c];

        dfs(r,c+1, max+t);

        for(int j=0;j<=i;j++)
            checked[r+j][c] = 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,0,0);
    printf("%d\n",answer);
}

 

3년전에는 예제들의 경우만 생각하여
같은 방향으로만 묶으면 된다고 생각했던 것 같다.

#include <cstdio>

int main() {
	int n, m; scanf("%d%d", &n, &m);
	int max = 0;
	char table[4][5];
	for (int i = 0; i < n; i++) {
		scanf("%s",table[i]);
	}	
	int t;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		t = 0;
		for (int j = 0; j < m; j++) {
			t = t * 10 + (table[i][j]-'0');
		}
		sum += t;
	}
	for (int i = 0; i < m; i++) {
		t = 0;
		for (int j = 0; j < n; j++) {
			t = t * 10 + (table[j][i]-'0');
		}
		max += t;
	}
	if (max < sum) max = sum;
		
	printf("%d", max);
}

 

이번에 풀때도 처음에 같은 생각을 했었지만, 반례가 있을 수 있다고 생각하여 완전탐색을 하였다.