글 읽기 - 틀린 케이스를 알려주세요 ㅠㅠ

jupiny 6년 전 0

코드에 대한 내용은 주석에 적어놓았습니다.

아래 코드가 통과하지 못하는 예외 케이스에는 어떤 경우가 있을까요?

#include <iostream>
#include <string>
using namespace std;

int board[101][101];

int N, M;
int ret = 0;

int cal_area(int y1, int x1, int y2, int x2) {
	int sum = 0;
	for(int i=y1; i<=y2; i++) {
		for(int j=x1; j<=x2; j++) {
			sum += board[i][j];
		}
	}
	return sum;
}

// 왼쪽 상단 모서리의 좌표가 (y, x)
// 이전까지의 합이 val
// 앞으로 더 선택해야될 직사각형의 수가 to_pick
void recursive(int y, int x, int val, int to_pick) {
	if(to_pick == 1) {
		int sum = cal_area(y, x, N-1, M-1);
		ret= max(ret, val*sum);
		return;
	}
    // 가로 모양의 직사각형을 선택할 때
	for(int i=y; i<N-1; i++) {
		int sum = cal_area(y, x, i, M-1);
		recursive(i+1, x, val*sum, to_pick-1);
	}
    // 세로 모양의 직사각형을 선택할 때
	for(int i=x; i<M-1; i++) {
		int sum = cal_area(y, x, N-1, i);
		recursive(y, i+1, val*sum, to_pick-1);
	}
}

int main() {
	cin >> N >> M;
	for(int i=0; i<N; i++) {
		string s;
		cin >> s;
		for(int j=0; j<M; j++) {
			board[i][j] = s[j] - '0';
		}
	}
	recursive(0, 0, 1, 3);
	cout << ret << endl;
}

2468ab 6년 전 0

제가 실력이 부족해서 코드 보고 반례나 잘못된거는 못 잡아 드리는데요

음 일단 최대 들오는 숫자가 10000개인데 그 모든 수가 9라고 생각하고 각 직사각형에 3333개씩 들어가게 되면 대략 각 직사각형당 30000의 값이되는데 이러면 3000^3 하면

int 범위를 넘지 않을까 싶네요

그리고 다음으로 매번 합을 구하는 함수를 호출하시는 거 같은데

1차원에서 연속된 수의 합은 구할때 미리 sum이라는 배열을 저장해서 j~i 까지의 합을 구할때 sum(i) - sum(j-1) 이라는 방식을 사용하듯이

2차원에서 sum[i][j]라는 배열을 만드시면 cal_area 이 함수도 사용 안하셔도 될거같아요 이문제에서는 굳이 신경 안쓰셔도 될거같지만요

더 못도와드려서.. ㅠㅠ

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

문제

문제

출처

ICPC

틀린 케이스를 알려주세요 ㅠㅠ

jupiny 6년 전 0

2468ab 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말