[C++] 백준 16235번: 나무 재테크

🔗 문제

16235번: 나무 재테크

16235번: 나무 재테크

제한

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ N^2
• 1 ≤ K ≤ 1,000
• 1 ≤ A[r][c] ≤ 100
• 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
• 입력으로 주어지는 나무의 위치는 모두 서로 다름

 

🖍 풀이

처음에는 나무를 list에 저장하고 폐사할 경우 -1로 표기하고 해마다 정렬했는데 시간초과였다.

나이 오름차순으로 양분을 먹이려고 정렬을 이용했고, 새로 생기는 나무를 push_front()로 넣어도 시간초과였다. 

정렬이 문제인 것 같아서 아예 나무 저장방식을 바꿨다. 

 

 

 

 

3차원 배열을 이용했다. N이 최대 10이고 초기 나이값 최대 10 + K 최대 1000이라  할 수 있는 무식한 풀이 방법인 것 같다.

-> O(1010 + N^2 * K)..... ?? 

 

• map[x][y][0] : (x, y)위치의 양분값
• map[x][y][age]: (x, y)위치에 age살 나무의 개수

1. init(): 밭에 초기 양분을 5씩 저장한다.
2. spring(): 나무 한그루씩 양분값과 비교해서 나이 먹어야 하는 애들이랑 양분 값을 tmp에 저장한다. map에서 바로 나이를 올리면 중복해서 나이를 먹기 때문에 tmp라는 임시 저장공간을 사용한다.
3. summer(): tmp에 저장된 애들을 map에 적용시킨다.
4. autumm(): 나이를 5부터 5씩 올리면서 [x][y][age]수만큼 주변 8개에 나무를 심는다.
5. winter(): A에 저장한 양분값을 map에 추가
6. 과정2~5를 K번 반복한다.
7. 삼중포문을 돌며 모든 나무 수를 더한 값을 출력한다.

 

시간을 더 줄이고 싶은데 좋은 방법 생각나면 다시 풀어보고 싶다 

특히 MAX_AGE까지 반복문 도는거 진짜 별로라고 생각했는데 리스트 정렬하는 시간 빠르다는 사실을 믿을 수가 없다. 

 

💾  소스

#include <iostream>

const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

const int MAX_AGE = 1011;

int N, M, K;
int A[11][11];
int tmp[11][11][MAX_AGE] = {0, };
int map[11][11][MAX_AGE];

void init()
{
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<=N; ++j)
        {
            map[i][j][0] = 5;
        }
    }
}

void spring()
{
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<=N; ++j)
        {
            for(int age=1; age<MAX_AGE; ++age)
            {
                if(map[i][j][age] == 0)
                    continue;
                
                while(map[i][j][age] > 0)
                {
                    if(map[i][j][0] >= age)
                    {
                        map[i][j][0] -= age; // 나이만큼 양분 먹기
                        map[i][j][age]--;
                        
                        tmp[i][j][age+1]++;
                    }
                    else
                    {
                        //사실 여기가 summer
                        tmp[i][j][0] += (map[i][j][age]*(age/2));
                        map[i][j][age] = 0;
                    }
                }

            }
        }
    }
}

void summer()
{
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<=N; ++j)
        {
            for(int age=0; age<MAX_AGE; ++age)
            {
                map[i][j][age] += tmp[i][j][age];
                tmp[i][j][age] = 0;
            }
        }
    }
}

void autumn()
{
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<=N; ++j)
        {
            for(int age=5; age<MAX_AGE; age+=5)
            {
                if(map[i][j][age] == 0)
                    continue;
            
                for(int d=0; d<8; ++d)
                {
                    int x = dx[d] + i;
                    int y = dy[d] + j;

                    if(x>0 && y>0 && x<=N && y<=N)
                        map[x][y][1] += map[i][j][age];
                }
            }
        }

    }
}

void winter()
{
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<=N; ++j)
        {
            map[i][j][0] += A[i][j];
        }
    }
}

void solve()
{
    init();
    while(K--)
    {
        spring();
        summer();
        autumn();
        winter();
    }
    
    return;
}

int main()
{
    int answer = 0;

    std::cin >> N >> M >> K;
    
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<=N; ++j)
        {
            std::cin >> A[i][j];
        }
    }
    
    int x, y, z;
    for(int i=0; i<M; ++i)
    {
        std::cin >> x >> y >> z;
        map[x][y][z]++;
    }
    
    solve();
    
    
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<=N; ++j)
        {
            for(int age=1; age<MAX_AGE; ++age)
            {
                answer += map[i][j][age];
            }
        }
    }
    std::cout << answer;
    
    return 0;
}