[백준 16235번] 나무 재테크

문제 링크: 16235번 나무 재테크

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

 

전형적인 시뮬레이션 문제로서, 주어진 조건을 얼마나 꼼꼼하게 구현해내느냐가 중요하다. 웬일로 다른 풀이에 비해 메모리를 적게 사용하는 양질의 풀이를 뽑아냈는데, 아마 클래스를 정의하지 않고 ArrayList<Integer>의 2차원 배열로서만 나무를 표현했던 것이 주요한 것 같다(컴파일러가 경고를 주는데, 검색해보아도 이를 해결할 수 있는 방법이 없다고 하는 것 같다...).

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int m;
    static int k;
    static int[][] A;
    static int[] drow = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dcol = {-1, 0, 1, -1, 1, -1, 0, 1};

    public static void main(String[] args) throws IOException {

        /* input */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        A = new int[n][];
        for (int i = 0; i < n; i++)
            A[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        ArrayList<Integer>[][] trees = new ArrayList[n][n];
        for (int i = 0; i < n; i++) {
            trees[i] = new ArrayList[n];
            for (int j = 0; j < n; j++)
                trees[i][j] = new ArrayList<Integer>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            int age = Integer.parseInt(st.nextToken());
            trees[row-1][col-1].add(age);
        }

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                Collections.sort(trees[i][j]);

        int[][] norish = new int[n][n];
        for (int i = 0; i < n; i++)
            Arrays.fill(norish[i], 5);
        /* end of input*/



        for (int year = 0; year < k; year++) {
            /* spring, summer */
            for (int row = 0; row < n; row++) {
                for (int col = 0; col < n; col++) {
                    int dead = 0;

                    /* spring */
                    int treeIdx;
                    for (treeIdx = 0; treeIdx < trees[row][col].size(); treeIdx++) {
                        int curTreeAge = trees[row][col].get(treeIdx);
                        if (norish[row][col] < curTreeAge)
                            break; // 나무가 오름차순으로 정렬되었기에
                            	   // 지금 나무가 양분이 부족하면
                                   // 뒤의 나무도 당연히 부족하다.
                                   
                        // 충분한 양분이 있다면
                        norish[row][col] -= curTreeAge; // 양분은 감소하고
                        trees[row][col].set(treeIdx, curTreeAge + 1); // 나무 나이는 1 증가
                    }

                    // treeIdx==n이면 n그루가 양분을 먹었다는 의미임
                    // treeIdx < trees[row][col].size()이면 모든 나무가 영양분을 다 먹은 게 아님
                    // treeIdx==trees[row][col].size()가 되어야 함
                    while (treeIdx < trees[row][col].size()) {
                        dead += (trees[row][col].get(trees[row][col].size() - 1) / 2);
                        trees[row][col].remove(trees[row][col].size() - 1);
                    }

                    /* summer */
                    norish[row][col] += dead;
                }
            }

            /* autumn */
            for (int row = 0; row < n; row++) {
                for (int col = 0; col < n; col++) {
                    int numTreeToBreed = 0; // 번식할 나무의 개수
                    for (int age : trees[row][col])
                        if (age % 5 == 0)
                            numTreeToBreed++;

                    // 주변 8칸에 칸마다 나이 1인 나무를 numTreeToBreed개만큼 추가
                    for (int d = 0; d < 8; d++) {
                        int nr = row + drow[d];
                        int nc = col + dcol[d];
                        if (nr < 0 || nc < 0 || nr > n - 1 || nc > n - 1) continue;

                        for (int n = 0; n < numTreeToBreed; n++)
                            trees[nr][nc].add(0, 1); // 나이가 1인 나무 추가
                            						 // 오름차순으로 정렬되어야 하니까 인덱스 0에 추가
                    }
                }
            }

            /* winter */
            for (int row = 0; row < n; row++)
                for (int col = 0; col < n; col++)
                    norish[row][col] += A[row][col];
        }



        // after k years
        int numTreesAlive = 0;
        for (int row = 0; row < n; row++)
            for (int col = 0; col < n; col++)
                numTreesAlive += trees[row][col].size();
        System.out.println(numTreesAlive);
    }
}