[Java] 백준 16235번 : 나무 재테크*

1. 문제

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

16235번: 나무 재테크

 

 

 

2. 풀이 과정

1. 정렬 알고리즘이 필요없다.

삽입되는 값이 제일 작기 때문에, 순서대로 넣어주면 정렬된 상태이다. 차례대로 list에 add하면 내림차순으로 정렬되므로 뒤에서부터 탐색하도록 for문을 작성했다.

 

2. LinkedList vs ArrayList

순서대로 조회하는 일이 많으므로 ArrayList가 훨씬 효율적이다. 이 문제에서는 LinkedList로 풀이를 하면, 시간 초과가 난다.

 

3. 봄, 여름, 가을, 겨울 순서를 지키기 X

각 좌표마다 tree들을 저장하여 순서대로 탐색하며, 한 번에 처리할 수 있는 부분은 같이 처리해주었다. tree를 무작위로 한 list에 넣을 경우 이런 연산이 불가능하다.

 

import java.io.*;
import java.util.*;

public class Main {
	static int n, refill[][], feedmap[][];
	static ArrayList<Integer> trees[][];
	
	public static void simulation(int year) {
		int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
		
		for(int i=0; i<year; i++) {
			ArrayList<int[]> babyTrees = new ArrayList<>();
			//봄, 여름
			for(int a=1; a<=n; a++) {
				for(int b=1; b<=n; b++) {
					int treefeed = 0;//죽은 나무 양분
					int babyCnt = 0;//5의 배수인 수
					for(int c = trees[a][b].size()-1; c>=0; c--) {
						int age = trees[a][b].get(c);
						if(feedmap[a][b] < age) {
							treefeed+=age/2;
							trees[a][b].remove(c);
						}
						else {
							feedmap[a][b] -= age++;
							trees[a][b].set(c, age);
							if(age%5==0) {//가을
								babyCnt++;
							}
							
						}
					}
					feedmap[a][b] += treefeed + refill[a][b];//겨울
					babyTrees.add(new int[] {a, b, babyCnt});
				}
			}
			
			for(int[] bt : babyTrees) {
				for(int f=0; f<8; f++) {
					int nx = bt[0]+dx[f];
					int ny = bt[1]+dy[f];
					int cnt = bt[2];
					if(0<nx && nx<=n && 0<ny && ny<=n) {
						while(cnt-->0) {
							trees[nx][ny].add(1);
						}
						
					}
				}
			}			
		}
			
	}
	
	
	public static void main(String[] args) throws Exception {
		//0. init
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		trees = new ArrayList[n+1][n+1];
		refill = new int[n+1][n+1];
		feedmap = new int[n+1][n+1];
		
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=n; j++) {
				//input
				refill[i][j] = Integer.parseInt(st.nextToken());
				//init
				trees[i][j] = new ArrayList<>();
				feedmap[i][j] = 5;
				
			}
		}
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			trees[x][y].add(z);
		}
		
		//1. simulation
		simulation(k);
		int result = 0;
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				result += trees[i][j].size();
			}
		}
		System.out.println(result);
	}
}

 

결과