백준 16235 나무재태크

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

16235번: 나무 재테크

나무재태크 풀이정말 너무합니다. 5개월전까지 통과했던 소스가 시간초과라니....

0.3초 시간제한으로 바뀌어버린 나무재태크 어떻게 해결했을까요?

 

처음에는 삼차원 배열을 이용해서 나무를 각 땅에 여러개 넣었습니다. 직관적으로 보기에도

편한 방법이지만 시간 제한이 바뀌고 난 후에 시간 초과가 걸린만한 곳은 3차원배열을 사용

하고 각 땅위치에서 나무가 몇개있는지 매번 세고 앉아있어서 그런것이 아닐까 의심을 해봤습니다.

 

간단히 나무재태크 풀이에 대해서 먼저 설명해 드리겠습니다.

우선 초기 땅은 5로 N * N 배열에 들어가 있는 상태에서

겨울에 로봇이 뿌릴 양분이 담긴 배열을 입력을 받습니다.

그리고 M은 현재 사용자가 심은 나무들의 위치로 위치 y, x 값과 나이를 입력을 받고

k년이 되는 시점에 나무가 몇개 있는지 파악하는 문제입니다.

 

나무는 현재나이만큼 땅의 양분을 흡수 하면 한살씩 나이를 먹게 되고

양분이 나이보다 부족하게되면 죽고 양분으로 바뀌게 되는데 자신의 나이에서 /2 한 값이 양분으로 바뀝니다.

간단한 각 배열방마다 양수 인지 음수가 되는지 따져가면서 양수면 한살 증가시키고 양분을 그만큼 줄이고

음수가 되면 나무를 양분으로 바꾸면 되겠죠? 그렇게 하면 봄과 여름이 해결됩니다.

 

그리고 가을은 번식하는 계절로 각 0,0 부터  전체 배열을 돌면서 나무의 나이가 5의 배수인것을 찾고 

8개의 방향으로 1살짜리 나무를 추가하면됩니다. 실제적으로 소스를 짜는게 어렵지 않나? 생각하실수 있지만

간단합니다.

 

겨울은 처음에 로봇이 뿌릴 양분을 입력받은 배열을 그냥 그 위치마다 추가해주면서 K번 만큼 돌리고 

마지막에 남은 나무의 갯수를 세고 출력을 하면 끝 인데....

사실 소트도 해야하고 탐색같이 갈수있는 위치를 파악해서 추가해줘야하고 그걸 또 매번확인해야하니 

어렵긴 합니다. 

그렇지만 우리에게는 stl 이있다는것~ 

시간제한이 0.3초로 바뀌었지만 3차원 배열로 한 소스를 보고 백터배열을 이용한 방법을 소개로 글을 마치겠습니다. 

 

#include<stdio.h>
#include<algorithm>
using namespace std;
int N, M, K, A[14][14], cA[14][14];
int tree[14][14][2004];
int death[14][14];
int dy[] = { -1,-1,-1,0,0,1,1,1 };
int dx[] = { -1,0,1,-1,1,-1,0,1 };
int main(void)
{
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            int data;
            scanf("%d", &data);
            A[i][j] = 5;
            cA[i][j] = data;
        }
    }
    for (int i = 1; i <= M; i++)
    {
        int y, x, data;
        scanf("%d %d %d", &y, &x, &data);
        tree[y][x][0] = data;
    }
 
    for (int c = 0; c < K; c++)
    {
        //봄, 여름
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (tree[i][j][0] != 0)
                {
                    int idx = 0;
                    while (tree[i][j][idx] != 0 && tree[i][j][++idx] != 0);
                    sort(tree[i][j], tree[i][j] + idx);
                    for (int ii = 0; ii < idx; ii++)// 양분주기
                    {
                        if (A[i][j] - tree[i][j][ii] >= 0)// 양분이 충분한경우
                        {
                            A[i][j] = A[i][j] - tree[i][j][ii];// 양분 흡수
                            tree[i][j][ii]++;
                        }
                        else if (A[i][j] - tree[i][j][ii] < 0)
                        {
                            while ((A[i][j] - tree[i][j][ii] < 0) && (ii != idx))// 양분이 부족하다면->여름에할일해버림
                            {
                                death[i][j] += tree[i][j][ii] / 2;// 여름에 할일 까지 끝냄
                                tree[i][j][ii] = 0;
                                ii++;
                            }
                        }
                    }
                }
                A[i][j] += death[i][j];
                death[i][j] = 0;
            }
        }
 
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                
                    for (int ii = 0; tree[i][j][ii] != 0; ii++)
                    {
                        if (tree[i][j][ii] != 0 && tree[i][j][ii] % 5 == 0)//비어있지 않고 5의 배수라면
                        {
                            for (int k = 0; k < 8; k++)
                            {
                                int ny = i + dy[k];
                                int nx = j + dx[k];
                                if (0 < ny && ny <= N && 0 < nx && nx <= N)// 범위에 벗어나지 않는다면
                                {
                                    int iidx = 0;
                                    while (tree[ny][nx][iidx] != 0 && tree[ny][nx][++iidx] != 0);
                                    tree[ny][nx][iidx] = 1;
                                }
                            }
                        }
                    }
            
            }
        }
        int cnt = 0;
        //겨울 양분 주기
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (tree[i][j][0] != 0) cnt++;
                A[i][j] += cA[i][j];
            }
        }
        if (cnt == 0) break;
    }
    int cnt = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            int idx = 0;
            while (tree[i][j][idx] != 0 && tree[i][j][++idx] != 0);
            cnt += idx;
        }
    }
    printf("%d\n", cnt);
 
    return 0;
}

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int N, M, K;//각변 길이,심은나무갯수,지나야하는 년도 
int input[104][104];// 입력 토지
int map[104][104]; // 초기 토지
int SummerSoil[104][10];//죽은 양분
vector <int> tree[104][104];
int dy[] = { -1,-1,-1,0,0,1,1,1 };
int dx[] = { -1,0,1,-1,1,-1,0,1 };
 
int main(void)
{
    scanf("%d %d %d",&N,&M,&K);
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            map[y][x] = 5;
            scanf("%d",&input[y][x]);
        }
    }
    for (int i = 0; i < M; i++) {
        int r, c,age;
        scanf("%d %d %d", &r, &c,&age);
        tree[r - 1][c - 1].push_back(age);
    }
    while (K--) {
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                sort(tree[y][x].begin(), tree[y][x].end());
                for (int TreeCnt = 0; TreeCnt < tree[y][x].size(); TreeCnt++) {
                    int cur = tree[y][x][TreeCnt];
                    if (cur <= map[y][x]) {
                        map[y][x] -= cur;
                        tree[y][x][TreeCnt]++;
                    }
                    else {
                            tree[y][x].erase(tree[y][x].begin() + TreeCnt);
                            SummerSoil[y][x] += cur / 2;
                            TreeCnt--;
                        }
                }
            }
        }/////////////////////////봄
 
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                map[y][x] += SummerSoil[y][x];
                SummerSoil[y][x] = 0;
            }
        }//////////////////////////여름
 
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                for (int TreeCnt = 0; TreeCnt < tree[y][x].size(); TreeCnt++) {
                    if (tree[y][x][TreeCnt] % 5 == 0) {
                        for (int dir = 0; dir < 8; ++dir) {
                            int ny = y + dy[dir];
                            int nx = x + dx[dir];
                            if (0 <= ny && ny < N && 0 <= nx && nx < N) {
                                tree[ny][nx].push_back(1);
                            }
                        }
                    }
                }
            }
        }////////////가을
 
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
 
                map[y][x] += input[y][x];
            }
        }///////////  겨울
 
    }
    int ret = 0;
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            ret += tree[y][x].size();
        }
    }
    printf("%d\n", ret);
    return 0;
}

덜 복잡하지만 그래도 성공한 소스이니 이쁘게 봐주세요.

 

이것이 양분으로 만들어주는 소스인데 첨에 보면 왜 TreeCnt -- 하지 하는데 tree[y][x][TreeCnt] 값을 없애기때문에 

하나씩 줄여줘야합니다.

 

그래도 이해가 안된다면 2가지방법을 이용해서 해도되니 참고해주세요

 

1. 그위치에서 나머지 트리양분으로 바꾸고 그위치에서 끝인것 erase를 이용해서 없애기

2. erase 사용 안하고 pop_back를 해주는 방식 

제일 아래것이 백터로 푼것에서 TreeCnt--를 한 방식이고 위로 차례대로 입니다.

마지막에 소개한 두개 방식은 확실히 더 빠르고 하네요. 이해되는것 쓰셔도됩니다.

 

다들 힘내셔서 나무재태크 넘겨봅시다. 이상 입니다.