글 읽기 - C++)더 효율적인 방법에는 무엇이 있을까요(주석 있음)

rootsquare 3년 전 0

문제에 나와있는 설명대로 코딩을 해 보았으나 시간 초과가 납니다.
혹시 더 효율적인 풀이는 무엇이 있을끼요?
#include<stdio.h>
#include<vector>
#include<deque>
using namespace std;
deque<int> land[12][12];//땅에 심어진 나무들을 저장하는 큐 배열.
int imove[8]={-1,-1,0,1,1,1,0,-1};//나무 번식시킬때 좌표 이동.
int jmove[8]={0,1,1,1,0,-1,-1,-1};
int land_code(int x,int y,int width);
int range(int x,int xrange,int y,int yrange);
int main(void)
{
    int width,start,years,i,j,k,l,m,roll,now,answer=0;
    int si,sj,ti,tj,age,death=0;
    int now_food[12][12]={0};//현재 땅에 남아있는 양분.
    int add_food[12][12]={0};//겨울마다 추가할 양분.
    int now_tree[12][12]={0};//현재 땅에 남아있는 나무 수.
    int add_tree[12][12]={0};//현 시점에서 새로 추가된 나무의 수.
    scanf("%d %d %d",&width,&start,&years);//땅의 크기,시작할 떄 나무의 개수,증식 년수를 입력받는다.
    for(i=1; i<=width; i++)
    {
        for(j=1; j<=width; j++)
        {
            now_food[i][j]=5;//처음에는 모든 땅에 양분 5를 넣는다.
            scanf("%d",&add_food[i][j]);//겨울마다 해당 땅에 추가할 양분을 입력받는다.
        }
    }
    for(i=1; i<=start; i++)
    {
        scanf("%d %d %d",&si,&sj,&age);//초기 나무의 위치와 나이를 입력받는다.
        land[si][sj].push_back(age);//땅의 해당 좌표에 넣어준다.
        now_tree[si][sj]++;//그 땅의 나무수를 1 늘린다.
    }
    answer=start;
    for(k=1; k<=years; k++)//정해진 년도동안 반복한다.
    {
        for(i=1; i<=width; i++)
        {
            for(j=1; j<=width; j++)
            {
                death=0;
                roll=now_tree[i][j];//현재 땅에 있는 나무 수만큼 돌린다.
                for(m=1; m<=roll; m++)//그 땅에 있던 나무들을 조사한다.
                {
                    now=land[i][j].front();//현재 나무의 나이. 문제 조건상 가장 어린 나무부터 뽑는다.
                    land[i][j].pop_front();//그 나무를 치운다.
                    if(add_tree[i][j]==0)//이 나무가 원래부터 있던 나무라면
                    {
                        if(death==0 && now_food[i][j]-now>=0)//만일 양분이 충분히면(봄 행동)
                        {
                            now_food[i][j]-=now;//그 나무에게 양분을 먹인다.
                            now+=1;//그 나무의 나이를 1 올린다.
                            land[i][j].push_back(now);//나무를 키워서 큐에 넣는다.
                            if(now%5==0)//키운 나무가 번식기가 되면
                            {
                                for(l=0; l<=7; l++)
                                {
                                    ti=i+imove[l];
                                    tj=j+jmove[l];
                                    if(range(ti,width,tj,width)==1)//만일 나무가 번질 수 있는 땅이라면
                                    {
                                        land[ti][tj].push_front(1);//큐에 1을 넣어준다.
                                        now_tree[ti][tj]++;//그 땅의 나무 수를 1 늘린다.
                                        answer++;//정답 1 증가
                                        if(land_code(ti,tj,width)>land_code(i,j,width))//이미 조사한 땅은 또 조사할 필요가 없으므로, 현재 땅보다 땅 번호가 더 큰 땅(for문 돌렸을 때 현재보다 나중에 조사하는 땅)만 add를 써준다.
                                        {
                                            add_tree[ti][tj]++;//그 땅의 증가된 나무 수를 1 늘린다.
                                        }
                                    }
                                }
                            }
                        }
                        else//부족하면(이러면 해당 칸에서 이 나무 이후 모든 나무는 다 죽는다.)
                        {
                            death=1;
                            answer--;
                            now_tree[i][j]--;
                            now_food[i][j]+=(now/2);//죽은 나무 나이의 절반을 양분으로 넣는다.(여름 행동)
                        }
                    }
                    else//이 나무가 새로 추가된 나무라면
                    {
                        add_tree[i][j]--;
                        land[i][j].push_back(now);//새로 추가된 나무는 다음 년도부터 성장을 시작하므로, 얘는 따로 빼준다.
                    }
                }
                add_tree[i][j]=0;
                now_food[i][j]+=add_food[i][j];//(겨울 행동)그 땅에 양분을 넣는다.
            }
        }
    }
    printf("%d",answer);//최종 정답을 출력한다.
    return 0;
}
int land_code(int x,int y,int width)
{
    return (x-1)*width+y;
}
int range(int x,int xrange,int y,int yrange)
{
    if(x>=1 && x<=xrange)
    {
        if(y>=1 && y<=yrange)
        {
            return 1;
        }
    }
    return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

C++)더 효율적인 방법에는 무엇이 있을까요(주석 있음)

rootsquare 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
