백준 14391

문제링크

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

문제

풀이

재귀로 모든 경우를 탐색하며 해결했다.
각 위치에서 아래쪽으로 뻗는 경우와 오른쪽으로 뻗는 경우 두가지 경우에 대해 값을 탐색하였다.

시행착오

2중 반복문 안쪽에 재귀 진입하도록 작성했다가 시간 초과가 나서 다시 생각하고 더 효율적으로 재작성 하였다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
int n, m;
int maps[5][5];
bool vi[5][5];

int brute(int pos,int sumn) {	
	if (pos == n * m) return sumn;
	int x = pos / m;
	int y = pos % m;
	int r = 0;
	if (vi[x][y]) {
		r=max(r,brute(pos + 1,sumn));
	}
	else {
		int j = 0, temp = 0;
		for (int i = 0; i < n; i++) {
			if (x + i >= n) break;
			if (vi[x + i][y]) break;
			for (j = 0; j <= i; j++) vi[x + j][y] = true;
			temp *= 10;
			temp += maps[x + i][y];
			r = max(r, brute(pos + 1, sumn + temp));
			for (int k = 0; k < j; k++) vi[x + k][y] = false;
		}
		temp = j = 0;
		for (int i = 0; i < m; i++) {
			if (y + i >= m) break;
			if (vi[x][y + i]) break;
			for (j = 0; j <= i; j++) vi[x][y + j] = true;
			temp *= 10;
			temp += maps[x][y + i];
			r = max(r, brute(pos + 1, sumn + temp));
			for (int k = 0; k < j; k++) vi[x][y + k] = false;
		}
	}
	return r;
}

int main(void) {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin.ignore();
		for (int j = 0; j < m; j++) {
			maps[i][j] = getchar()-'0';
		}
	}
	cout<<brute(0, 0);
}

후기

방향은 금방 잡고 풀기 시작했는데 그래도 한참 붙잡고 있었다...
코테에 이런제 나오면 시간안에 풀 수 있을지 모르겠다.