글 읽기 - 7573 질문드립니다

jeoses 6년 전 0

7573번 문제를 비주얼 스튜디오로 실행 했을 때 테스트 케이스에 대해서는 정답이 나오나

계속 런타임 에러가 뜨는데 반례가 생각나지 않습니다.

해당 코드에 대해서 런타임 걸리는 부분이 어디인지 찾을 수 없어서 질문드립니다 ㅠㅠ

#include<stdio.h>
#include<algorithm>

using namespace std;

int n, l, m, map[10001][10001],cnt = 0, max_value = 0, half = 0;
bool safe(int a, int b)
{
    return (1<= a && a<=n) && (1<= b && b<=n);
}
void input()
{
int a, b;

scanf("%d %d %d", &n, &l, &m); //n 맵 크기, ㅣ 그물 둘레, m 물고기 수

for (int i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
map[a][b] = 1;
}
half = (int)(l / 2);
}
void bfs(int a, int b)
{
int s = 1;
    int w;
while (s != (half))
{
         w = half - s;
        if(safe(a+(s-1), b+(w-1)))
        {
            cnt = 0;
    for (int i = 0; i < s; i++)
    {
    for (int j = 0; j < (half) - s; j++)
    {
    if (map[a+i][b+j] == 1){cnt++;}
    }
    }
    if (max_value <= cnt) max_value = cnt;
        }
s++;
}
}
void solve()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (map[i][j] == 1){bfs(i, j);}
}
}
printf("%d\n", max_value);
}
main()
{
input();
solve();
}

bupjae 6년 전 1

map 변수가 차지하는 용량은 10001 * 10001 * 4 = 약 381MB로 문제에서 요구한 메모리제한 128MB를 초과합니다.

jeoses 6년 전 0

bupjae님

댓글 달아 주셔서 감사합니다 ㅠㅠ

말씀해주신 부분 수정하기 위해서 map 2차원 배열을

입력 되는 n에따라 동적할당 하였는데

이번에는 메모리 초과 문제가 발생하네요.....

bupjae 6년 전 0

동적할당 한다고 해도 n = 10000 이 들어오면 결국 map 변수가 필요한 메모리는 앞선 계산과 마찬가지가 되죠.

좌표들을 저장할 다른 자료구조를 찾아보셔야 합니다.

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

문제

문제

출처

ICPC

7573 질문드립니다

jeoses 6년 전 0

bupjae 6년 전 1

jeoses 6년 전 0

bupjae님

bupjae 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말