글 읽기 - 재귀로 짯는데 잘모르겠습니다.

betain24 7년 전 0

일단 n*n으로 생각하고 짜고있습니다.

재귀로 d[i][j] = i, j을 오른쪽 모서리로 하는 최대 사각형의 한변의 길이입니다.

...

예제라도 나올것같았는데 안나오네요..

도움주시면 감사하겠습니다.

#include <stdio.h>
#include <algorithm>
using namespace std;

int n, m, ans = 0, d[1001][1001], a[1001][1001];
//일딴 n * m 말고 n*n 으로 돌리고잇습니다
int f(int x, int y){
	if(x < 1 || y < 1) return 0;
    // 2이상이면 갱신해준거라 그냥 리턴
	if(d[x][y] > 2) return d[x][y];
    
	for(int i=1;i<=n-x;i++){
	    //ck는 가로 세로열이 1인지 확인하는 것
        bool ck = true;
		for(int j=1;j<=n-x;j++){
			if(!a[x-j][y] || !a[x][y-j]){
				ck = false;
				break;
			}
		}	
        // temp에 다음값 저장
		int temp = f(x-i, y-i);
        // 가로 세로열, 자기자신이 모두 1이면 temp 값을 더한다
		if(ck && a[x][y]) d[x][y] += temp;
	}
	return d[x][y];
}
int main(){
	char c[1001];
	scanf("%d %d", &n, &m);
	for(int i=1;i<=n;i++){
		scanf("%s", c);
		for(int j=1;j<=m;j++){
			a[i][j] = d[i][j] = c[j-1]-'0';
		}
	}
	f(4, 4);
	/*for(int i=1;i<=max(n,m);i++){
		f(1, i);
		f(i, 1);
	}*/
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%d ", d[i][j]);
		}
		puts("");
	}
}

ljh6274 7년 전 1

지금 같은 경우는 f함수 내의 for문이 돌수 없습니다.

n이 4인데 for(int i=1; i <=n-x; i++)을 하게 되면 i가 1인데 0보다 작거나 같을때까지 돌기 때문이죠

d[i][j]를 i,j에서의 가장 큰 정사각형 이라고 하면 d[i][j]가 '1' 일때

점화식을 d[i][j] = min(d[i+1][j], d[i+1][j+1], d[i][j+1]) + 1 이렇게 두고 하시면 될거 같습니다.

질문하신 분께서 하시는 방식으로 하면 i+1, j+1 대신 i-1, j-1으로 하시면 될거 같습니다.

betain24 7년 전 1

@ljh6274

답변 감사합니다ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

재귀로 짯는데 잘모르겠습니다.

betain24 7년 전 0

ljh6274 7년 전 1

betain24 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말