16235번 나무 재테크

https://www.acmicpc.net/problem/16235

삼성 SW 역량 테스트 기출문제이다.

이 나무 재테크 문제의 풀이를 두 번 업로드 한 적이 있으나,

시간 제한이 0.3초로 단축되면서, 내 코드가 시간 초과를 받게 되었다.

그래서 다시 풀어보았다.

시간 초과의 내 코드는 봄, 여름, 가을, 겨울을

모두 이중 for문을 활용하여 각각에 적용하고 있었다. 즉, 이중 for문 4개를 사용하였었다.

하지만 시간을 줄이기 위해서는

어떤 사건과 또 다른 사건은 서로에게 영향이 없는걸 활용해야한다.

즉, 이중 for문 2개로 구현이 가능하다.

예시) 죽은 나무의 칸에 양분을 더하는 것이랑 각 칸에 추가될 양분(A[행][열])을 더하는 것은

서로 영향의 미침이 없다. 또한, 다른 위치에 영향도 없다.

즉, 자기 자신의 자리에만 영향이 있을 뿐 이다.

마찬가지로 번식도 미리 변수(child[행][열])을 계산하여, 그 값만큼만 insert 해주면 되는 것이다.

마지막으로 sort를 사용하면 (아마도) 시간 초과가 날 수도 있다.

그래서 나는 insert를 사용하였다.

시간 초과 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, M = 0, K = 0;
 
int dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int dx[8] = { 1, 1, 1, 0, -1, -1, -1, 0 };
 
typedef struct info
{
    int age;
    bool live;
}info;
 
typedef struct info2
{
    int add;
    int now;
}info2;
 
vector<info> tree[55][55];
 
info2 resource[55][55];
 
info temp;
 
void simulation()
{
    while (K--)
    {
        // 봄
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                for (int k = 0; k < tree[i][j].size(); k++)
                {
                    if (tree[i][j].at(k).live)
                    {
                        if (tree[i][j].at(k).age - resource[i][j].now > 0)
                        {
                            tree[i][j].at(k).live = false;
                            continue;
                        }
 
                        resource[i][j].now -= tree[i][j].at(k).age;
 
                        ++tree[i][j].at(k).age;
                    }
                }
        
        // 여름
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {            
                auto itr = tree[i][j].begin();
 
                while (itr != tree[i][j].end())
                {
                    if (!itr->live)
                    {
                        resource[i][j].now += itr->age / 2;
 
                        itr = tree[i][j].erase(itr);
                    }
                    else ++itr;
                }
            }
        
        // 가을
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                for (int k = 0; k < tree[i][j].size(); k++)        
                    if (tree[i][j].at(k).live && tree[i][j].at(k).age % 5 == 0)
                    {
                        for (int d = 0; d < 8; d++)
                        {
                            int y = i + dy[d];
                            int x = j + dx[d];
 
                            if (y < 0 || y >= N || x < 0 || x >= N) continue;
 
                            temp.age = 1;
                            temp.live = true;
 
                            tree[y][x].insert(tree[y][x].begin(), temp);
                        }
                    }
 
        // 겨울
        for (int i = 0; i < N; i++) 
            for (int j = 0; j < N; j++) 
                resource[i][j].now += resource[i][j].add;    
    }
}
 
int life()
{
    int ret = 0;
 
    for (int i = 0; i < N; i++) 
        for (int j = 0; j < N; j++) 
            for (int k = 0; k < tree[i][j].size(); k++)
                if (tree[i][j].at(k).live) 
                    ++ret;        
 
    return ret;
}
 
int main(void)
{
    int A = 0, y = 0, x = 0, age = 0;
 
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &A);
 
            resource[i][j].now = 5;
            resource[i][j].add = A;
        }
    
 
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d %d", &y, &x, &age);
 
        --y; --x;
 
        temp.live = true;
        temp.age = age;
 
        tree[y][x].push_back(temp);
    }
 
    simulation();
 
    printf("%d\n", life());
 
    return 0;
}
 

정답 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, M = 0, K = 0;
 
int dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int dx[8] = { 1, 1, 1, 0, -1, -1, -1, 0 };
 
typedef struct info
{
    int add;
    int now;
}info;
 
info resource[55][55];
 
vector<int> tree[55][55];
 
int child[55][55] = { 0, };
 
void simulation()
{
    while (K--)
    {
        memset(child, 0, sizeof(child));    
 
        vector<int> temp[55][55];
 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                int dead = 0; // 죽은 양분 저장
 
                for (int k = 0; k < tree[i][j].size(); k++)
                {
                    if (tree[i][j].at(k) - resource[i][j].now > 0)
                    {
                        dead += tree[i][j].at(k) / 2;
                        continue;
                    }
 
                    resource[i][j].now -= tree[i][j].at(k);
 
                    ++tree[i][j].at(k);
 
                    temp[i][j].push_back(tree[i][j].at(k));
 
                    if (tree[i][j].at(k) % 5 == 0)
                        for (int d = 0; d < 8; d++)
                        {
                            int y = i + dy[d];
                            int x = j + dx[d];
 
                            if (y < 0 || y >= N || x < 0 || x >= N) continue;
 
                            ++child[y][x]; // 여기서 insert하게 되면, size 달라짐
                        }
                }
 
                tree[i][j] = temp[i][j];
                resource[i][j].now += dead + resource[i][j].add;
                // 죽은 양분 및 각 칸에 추가될 양분
            }
 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                for (int k = 0; k < child[i][j]; k++)
                    tree[i][j].insert(tree[i][j].begin(), 1);
    }
}
 
int life()
{
    int ret = 0;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            ret += tree[i][j].size();
 
    return ret;
}
 
int main(void)
{
    int A = 0, y = 0, x = 0, age = 0;
 
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &A);
 
            resource[i][j].now = 5; // 가장 처음 양분
            resource[i][j].add = A; // 각 칸에 추가되는 양분
        }
 
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d %d", &y, &x, &age);
 
        --y; --x; // 행, 열 조심
 
        tree[y][x].push_back(age);
    }
 
    simulation();
 
    printf("%d\n", life());
 
    return 0;
}