글 읽기 - 1915번 틀렸습니다

mygm1302 5년 전 0

길이를 기준으로 해당 길이의 사각형이 존재하는지를 부분합을 이용해 확인하고, 이를 이용해 이분탐색하는 알고리즘입니다.

게시판의 모든 반례를 돌려봤을땐 정상적으로 작동했지만 제출시 틀렸습니다가 뜹니다.

나름대로 만들어서 집어넣어봐도 정상적으로 작동하는거 같습니다.

어디가 잘못된걸까요?

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
//#include <string.h>
using namespace std;
int map[1001][1001];
int psum[1001][1001];
int N,M;
bool check(int l)//길이가 l인 정사각형이 존재하는지 확인
{
	for(int i=0;i<=N-l;i++)
	for(int j=0;j<=M-l;j++)
	if(psum[i+l][j+l]-psum[i+l][j]-psum[i][j+l]+psum[i][j]==l*l)return true;
	return false;
}
int main(){
//	memset(dp,-1,sizeof(dp));
	scanf("%d %d",&N,&M);
	for(int i=1;i<=N;i++)
	for(int j=1;j<=M;j++)
	scanf("%1d",&map[i][j]);

	for(int i=1;i<=N;i++)
	for(int j=1;j<=M;j++)
	psum[i][j]=map[i][j]+psum[i][j-1]+psum[i-1][j]-psum[i-1][j-1];
//부분합 계산
    
    int left=0;
	int right=1000;
	while(left!=right){
		int mid=(left+right)/2+1;
		if(check(mid))left=mid;
		else right=mid-1;
	}//이분탐색
	printf("%d",left);
}

mygm1302 5년 전 0

문제에 길이가 아니라 넓이였습니다. 아오...

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

문제

문제

출처

ICPC

1915번 틀렸습니다

mygm1302 5년 전 0

mygm1302 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말