나무재테크_16235

문제 출처 : 나무재테크

파라미터 정리

NxN 전체 크기, 1x1은 한 칸의 크기 (r,c)는 (1,1)부터 시작함
M 나무개수
처음 양분은 모든 칸에 +5
A[r][c]는 추가 양분
K는 1년 루틴을 몇 회 실시하는 가
1년 루틴
봄 - 나이만큼 양분 먹고, 나이+1, 어린 나무부터 양분을 먹음, 양분을 먹지 못하면 죽음
여름 - 봄에 죽은 나무의 1/2이 양분으로 변함(정수만 취급)
가을 - 나무의 나이가 5의 배수일 경우 나무가 번식함, 인접한 8개 칸에 나이가 1인 나무가 생성
겨울 - 각 칸에 A[r][c]에 해당하는 양분이 추가됨
K년 후 전체 NxN에 살아있는 나무의 개수를 반환

간략한 과정

input_1 N, M, K를 입력받기 (1~N~10), (1~K~1000)
input_2 A[r][c] 입력받기 (~100)
input_3 나무의 정보 (x, y, z)를 M번 입력받기 (x,y)는 위치 (z)는 나무 나이

output k년 후 살아남은 나무의 수 반환하기

코드

시간단축 성공, 예제 및 제출 성공
벡터 Map[10][10]을 이용해서 만듦
vector<int< Map[x좌표][y좌표] = {첫번째 나무의 나이, 두번째 나무의 나이};

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,M,K;
int feed[10][10];// 추가 양분
int Field[10][10];//현재 땅 상황
vector<int> tree[10][10];

void make_tree(int row, int col){
    for(int i = row -1; i < row + 2; i++)
        for(int j = col - 1; j < col + 2; j++){
            if((i < 0) || (j < 0) || (i > N-1) || (j > N-1)) continue;
            if((i == row) && (j == col)) continue;
            
            tree[i][j].push_back(1);
        }
            
}

int solve(){
    int res = 0;
    
    do{
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
            	//시작 전 나무 나이 순서대로 정렬
                sort(tree[i][j].begin(), tree[i][j].end());
                for(int k = 0; k < tree[i][j].size(); k++){
                   int n_age = tree[i][j][k];
                   
                   if(n_age <= Field[i][j]){//충분한 양분이 있을 때
                   		//봄
                       Field[i][j] -= n_age;
                       tree[i][j][k]++;
                       n_age++;
                   }else{//양분이 부족할 때
                        //마지막 벡터~현재 k값 벡터까지 차례대로 삭제
                        int end_p = k, k_size = tree[i][j].size() ;
                        for(int t = k_size-1; t >= k; t--){
                            //여름
                            n_age = tree[i][j][t];
                            Field[i][j] += (n_age/2);
                            //봄
                            tree[i][j].pop_back();
                        }
                        //해당 칸에 있는 나무를 모두 삭제했기 때문에 다음 칸으로 넘어감 
                        break;
                   }
                }
                //겨울
                Field[i][j] += feed[i][j];
            }
        }
        
        //가을, 다른 칸에 영향을 미치기때문에 ij for문 끝내고 따로 돌림
        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][k]%5 == 0)  make_tree(i,j);
            
        K--;
        
    }while(K>0);
    
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            res += tree[i][j].size();
    
    return res;
}

int main()
{
    cin >> N >> M >> K;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++){
            cin >> feed[i][j];
            Field[i][j] = 5;
        }
        
        
    for(int i = 0; i < M; i++){
        int x,y,z;
        cin >> x >> y >> z;
        tree[x-1][y-1].push_back(z);
    }

    cout<<solve()<<endl;
    
    return 0;
}

시행착오

백업_0603_pm01:23
테스트 통과한거랑 코드 똑같은 거 같은데 예제 오류 발생함;;
이유를 모르겟음

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> trees[10][10];
int N,M,K;
int feed[10][10];//겨울 양분
int Map[10][10];//현재 맵 상태

void bear(int r, int c){
    for(int i = r-1; i < r+2; i++){
        for(int j = c-1; j < c+2; j++){
            if(i < 0 || j < 0 || i > N-1 || j > N-1) continue;
            if(i==r && j==c) continue;
            trees[i][j].push_back(1);
        }
    }
    return;
}

int solve(){
    int res = 0;
    memset(Map,5,sizeof(Map));
    
    do{
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                sort(trees[i][j].begin(), trees[i][j].end());
                int size = trees[i][j].size();
                for(int k = 0; k < size; k++){
                    int nage = trees[i][j][k];
                    if(nage <= Map[i][j]){
                        Map[i][j] -= nage;
                        trees[i][j][k]++;
                    }else{
                        
                        for(int t = size-1; t >= k; t--){
                            nage = trees[i][j][t];
                            Map[i][j] += (nage/2);
                            trees[i][j].pop_back();
                        }
                        break;
                    }
                }
                Map[i][j] += feed[i][j];
            }
        }
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int  k = 0; k < trees[i][j].size(); k++)
                    if(trees[i][j][k]%5 == 0) bear(i,j);
        
        K--;
    }while(K!=0);

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            res += trees[i][j].size();
            
    return res;
}

int main()
{
    cin >> N >> M >> K;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> feed[i][j];
        
    for(int i = 0; i < M; i++){
        int x,y,z;
        cin >> x >> y >> z;
        trees[x-1][y-1].push_back(z);
    }
    
    cout << solve() << endl;

    return 0;
}

테스트는 통과하는데 시간초과됨,,,

#include <iostream>
#include <list>

using namespace std;

struct Tree{
  int r, c, age;
};

int N,M,K;
int feed[10][10];// 추가 양분
int Field[10][10];//현재 땅 상황
list<Tree>  Trees;

void make_tree(int row, int col){
    for(int i = row -1; i < row + 2; i++)
        for(int j = col - 1; j < col + 2; j++){
            if((i < 0) || (j < 0) || (i > N-1) || (j > N-1)) continue;
            if((i == row) && (j == col)) continue;
            
            Trees.push_front({i,j,1});
        }
            
}

int solve(){
    int res = 0;
    
    do{
        //봄
        for(auto iter = Trees.begin(); iter != Trees.end(); ){
            int n_age = iter->age;
            int n_row = iter->r;
            int n_col = iter->c;
            if( n_age <= Field[n_row][n_col]){
                Field[n_row][n_col] -= n_age;
                iter->age++;
                n_age ++;
                //가을
                if(n_age%5 == 0){
                    make_tree(n_row, n_col);
                }
                iter++;
            }else{//여름 같이 처리함
                Field[n_row][n_col] += (n_age/2);
                iter = Trees.erase(iter);
            }

        }
        //겨울
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                Field[i][j] += feed[i][j];
                
        K--;
    }while(K>0);
    
    res = Trees.size();
    return res;
}

int main()
{
    cin >> N >> M >> K;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++){
            cin >> feed[i][j];
            Field[i][j] = 5;
        }
        
        
    for(int i = 0; i < M; i++){
        int x,y,z;
        cin >> x >> y >> z;
        Trees.push_back({x-1,y-1,z});
    }

    cout<<solve()<<endl;
    
    return 0;
}

벡터로 만들어봄, iterator 사용해서 값 증가,삭제 시켜봄
예제 7 실행시 57나옴, 정답은 13
예제 8 실행시 50 나옴, 정답은 85

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,M,K;
int feed[10][10];// 추가 양분
int Field[10][10];//현재 땅 상황
vector<int> tree[10][10];

void make_tree(int row, int col){
    for(int i = row -1; i < row + 2; i++)
        for(int j = col - 1; j < col + 2; j++){
            if((i < 0) || (j < 0) || (i > N-1) || (j > N-1)) continue;
            if((i == row) && (j == col)) continue;
            
            tree[i][j].push_back(1);
        }
            
}

int solve(){
    int res = 0;
    
    do{
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                sort(tree[i][j].begin(), tree[i][j].end());
                for(auto iter = tree[i][j].begin(); iter != tree[i][j].end();){
                    int n_age = *iter;
                    int n_row = i, n_col = j;
                    
                    if( n_age <= Field[n_row][n_col]){//양분 충족될 때
                        Field[n_row][n_col] -= n_age;
                        (*iter)++;
                        n_age ++;
                        //가을
                        if(n_age%5 == 0)    make_tree(n_row, n_col);
                        iter++;
                    }else{//양분 충족 안될 때 //여름 같이 처리함
                        Field[n_row][n_col] += (n_age/2);
                        iter = tree[i][j].erase(iter);
                        //iter = Trees.erase(iter);
                        //iter++;
                    }
                }
            
                Field[i][j] += feed[i][j];
            }
        }
            
        K--;
        
    }while(K>0);
    
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            res += tree[i][j].size();
    
    return res;
}

int main()
{
    cin >> N >> M >> K;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++){
            cin >> feed[i][j];
            Field[i][j] = 5;
        }
        
        
    for(int i = 0; i < M; i++){
        int x,y,z;
        cin >> x >> y >> z;
        tree[x-1][y-1].push_back(z);
    }

    cout<<solve()<<endl;
    
    return 0;
}