글 읽기 - 시간초과..

dannydino 4년 전 0

값은 제대로 나오는 것 같습니다..

실행시간을 단축할 방법이 더 있을까요?

#include<iostream>

bool arr[15][15];
int sum,N;
bool y_check[15];

bool CanAllocate(int x,int y)
{

    for(int i=0;i<N;i++)
    {
        if(arr[x][i])
            return false;
        if(arr[i][y])
            return false;
    }
    int tmpx=x,tmpy=y;
    while(tmpx>=0&&tmpy>=0)
    {
        if(arr[tmpx--][tmpy--])
            return false;
    }
    
    tmpx=x,tmpy=y;
    while(tmpx<N&&tmpy<N)
    {
        if(arr[tmpx++][tmpy++])
            return false;
    }
    
    tmpx=x,tmpy=y;
    while(tmpx<N&&tmpy>=0)
    {
        if(arr[tmpx++][tmpy--])
            return false;
    }
    
    tmpx=x,tmpy=y;
    while(tmpx>=0&&tmpy<N)
    {
        if(arr[tmpx--][tmpy++])
            return false;
    }
    
    
    return true;
}

void Find(int x,int y,int leftNum)
{
    if(leftNum>=1)
    {
        for(int i=x+1;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(!y_check[j])
                {
                    if(CanAllocate(i,j))
                    {
                        y_check[j]=true;
                        arr[i][j]=true;
                        Find(i,j,leftNum-1);
                        y_check[j]=false;
                        arr[i][j]=false;
                    }
                }
            }
        }
    }
    else
    {
        sum++;
    }
}

void Find_Init()
{
    for(int i=0;i<N;i++)
    {
        y_check[i]=true;
        arr[0][i]=true;
        Find(0,i,N-1);
        y_check[i]=false;
        arr[0][i]=false;
    }
}



int main()
{
    std::cin>>N;
    if(N==1)
    {
        std::cout<<1<<std::endl;
        return 0;
    }
    Find_Init();
    std::cout<<sum<<std::endl;
    
    return 0;
}

dannydino 4년 전 0

Find함수에서 y는쓰지도않고 불필요하게 모든줄을검사했네요

바로 밑줄만 검사하게하니 통과되네요

#include<iostream>

bool arr[15][15];
int sum,N;
bool y_check[15];

bool CanAllocate(int x,int y)
{

    for(int i=0;i<N;i++)
    {
        if(arr[x][i])
            return false;
        if(arr[i][y])
            return false;
    }
    int tmpx=x,tmpy=y;
    while(tmpx>=0&&tmpy>=0)
    {
        if(arr[tmpx--][tmpy--])
            return false;
    }
    
    tmpx=x,tmpy=y;
    while(tmpx<N&&tmpy<N)
    {
        if(arr[tmpx++][tmpy++])
            return false;
    }
    
    tmpx=x,tmpy=y;
    while(tmpx<N&&tmpy>=0)
    {
        if(arr[tmpx++][tmpy--])
            return false;
    }
    
    tmpx=x,tmpy=y;
    while(tmpx>=0&&tmpy<N)
    {
        if(arr[tmpx--][tmpy++])
            return false;
    }
    
    
    return true;
}

void Find(int x,int leftNum)
{
    x++;
    if(leftNum>=1)
    {
            for(int j=0;j<N;j++)
            {
                if(!y_check[j])
                {
                    if(CanAllocate(x,j))
                    {
                        y_check[j]=true;
                        arr[x][j]=true;
                        Find(x,leftNum-1);
                        y_check[j]=false;
                        arr[x][j]=false;
                    }
                }
            }
    }
    else
    {
        sum++;
    }
}

void Find_Init()
{
    for(int i=0;i<N;i++)
    {
        y_check[i]=true;
        arr[0][i]=true;
        Find(0,N-1);
        y_check[i]=false;
        arr[0][i]=false;
    }
}



int main()
{
    std::cin>>N;
    if(N==1)
    {
        std::cout<<1<<std::endl;
        return 0;
    }
    Find_Init();
    std::cout<<sum<<std::endl;
    
    return 0;
}

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

문제

문제

출처

ICPC

시간초과..

dannydino 4년 전 0

dannydino 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말