글 읽기 - 이거 시간복잡도가 4*m*n인데 왜 타임오버가뜨나요?

logeon0725 4년 전 0

이거 시간복잡도가 4*m*n인데 왜 타임오버가뜨나요?

#include<stdio.h>
int arr_map[1010][1010]={0};
int main()
{
    char arr_str[10]="ULRD";
    int gox[10]={0,-1,1,0};
    int goy[10]={-1,0,0,1};
    int MINX,MINY,MINN,a;
    int i,j,n,m,x,y;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a);
            if((i+j)%2==1 && MINN>a)MINN=a,MINX=i,MINY=j;
        }
    }
    if(m%2==0 && n%2==0)arr_map[MINX][MINY]=-1;
    x=1,y=1;
    arr_map[x][y]=-1;
    while(x!=n || y!=m)
    {
        for(i=0;i<4;i++)
        {
            if(arr_map[x+gox[i]][y+goy[i]]!=-1 && x+gox[i]>0 && y+goy[i]>0 && x+gox[i]<=n && y+goy[i]<=m)
            {
                x=x+gox[i];
                y=y+goy[i];
                printf("%c",arr_str[i]);
                arr_map[x][y]=-1;
                break;
            }
        }
    }
    return 0;
}
/*
3 3
5 1 3
2 4 8
1 1 2
*/

windflower 4년 전 0

while문의 시간복잡도가 4nm이 아니지 않을까요?

현재 코드에서는 방문했던 위치를 다시 방문할 수 있을 것 같습니다

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

문제

문제

출처

ICPC

이거 시간복잡도가 4mn인데 왜 타임오버가뜨나요?

logeon0725 4년 전 0

windflower 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말