[백준 - 16235] 골드4 - 나무재테크

www.acmicpc.net/problem/16235

16235번: 나무 재테크

로직이 쉽게 생각나서 별로 어렵지 않은 문제인줄 알았다. 하지만 시간초과 때문에 많이 고생한 문제다. 결국 지인 찬스

 

remove를 쓰면 안된다는걸 알게됐다.

 

ArrayList에서 remove로 제거하고, 땡겨오는 과정 때문에서 n번의 연산이 생겨서 쓰면 안된다. 

 

처음 짠 로직에서 remove만 빼줬더니 시간초과를 해결했다.

 

1. 유형

시뮬

 

2. 풀이

나무 클래스를 만들어서 4계절을 탐색해주면 된다.

 

가장 까다로운 부분은 봄 이다. 이 과정에서 remove를 썼다가 시간초과의 늪에 빠졌다. 

 

temp 리스트를 따로 만들어서 저장 하는 방식으로 해결했다.

 

3. 코드

package 구현.삼성역태;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class back_16235나무재테크 {
	static int dr[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int dc[] = { -1, 0, 1, 1, 1, 0, -1, -1 };

	static class Tree implements Comparable<Tree> {
		int r, c, age;

		public Tree(int r, int c, int age) {
			super();
			this.r = r;
			this.c = c;
			this.age = age;
		}

		@Override
		public int compareTo(Tree o) {
			return this.age - o.age;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int n, m, k;
		n = Integer.valueOf(st.nextToken());
		m = Integer.valueOf(st.nextToken());
		k = Integer.valueOf(st.nextToken());
		int eng[][] = new int[n][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < n; j++) {
				
				eng[i][j] = Integer.valueOf(st.nextToken());
			}
		}
		ArrayList<Tree> list = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int r = Integer.valueOf(st.nextToken()) - 1;
			int c = Integer.valueOf(st.nextToken()) - 1;
			list.add(new Tree(r, c,	Integer.valueOf(st.nextToken())));
		}
		// 나이순 정렬

		int map[][] = new int[n][n];// 처음 양분 초기화
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = 5;
			}
		}
		// K년만큼 탐색
		for (int year = 0; year < k; year++) {
			// 4계절
			// 봄
			//temp 리스트 생성
			ArrayList<Tree> temp = new ArrayList<>();
			ArrayList<Tree> death = new ArrayList<>();
			for (Tree tree : list) {
				// 나무를 돌면서 자리에 해당하는 양분이 나이 이상이면 먹기
				if (map[tree.r][tree.c] > 0 && map[tree.r][tree.c] >= tree.age) {
					map[tree.r][tree.c] -= tree.age;
					tree.age += 1;
					temp.add(new Tree(tree.r, tree.c, tree.age));
				} else {
					death.add(new Tree(tree.r, tree.c, tree.age));
				}
			}
			
			//여름
			for (int j = 0; j<death.size(); j++) {
				Tree tree = death.get(j);
				map[tree.r][tree.c] += (tree.age / 2);
			}
			
			//가을
			// 나무 탐색하고
			list.clear();
			for (Tree tree : temp) {
				if (tree.age % 5 == 0) {
					for (int j = 0; j < 8; j++) {
						// 아니면 나이1짜리 나무 추가
						int nr = tree.r + dr[j];
						int nc = tree.c + dc[j];
						// 다음좌표 이탈인지 확인
						if (nr < 0 || nr >= n || nc < 0 || nc >= n)
							continue;
						list.add(new Tree(nr, nc, 1));
					}
				}
			}
			list.addAll(temp);
			
			//겨울
			for (int j = 0; j < map.length; j++) {
				for (int j2 = 0; j2 < map.length; j2++) {
					map[j][j2] += eng[j][j2];
				}
			}
		} // k년 탐색
		System.out.println(list.size());
	}
}

 

봄

			ArrayList<Tree> temp = new ArrayList<>();
			ArrayList<Tree> death = new ArrayList<>();
			for (Tree tree : list) {
				// 나무를 돌면서 자리에 해당하는 양분이 나이 이상이면 먹기
				if (map[tree.r][tree.c] > 0 && map[tree.r][tree.c] >= tree.age) {
					map[tree.r][tree.c] -= tree.age;
					tree.age += 1;
					temp.add(new Tree(tree.r, tree.c, tree.age));
				} else {
					death.add(new Tree(tree.r, tree.c, tree.age));
				}
			}