백준 16235(BOJ 16235) 나무 재테크 JAVA

백준 16235 나무 재태크 - 삼성  SW 기출문제

 

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

16235번: 나무 재테크

 

1. 시간 초과에 대해서 신경을 써야 한다.

 

비효율적으로 짜게 되면 통과하지 못하는 모습을 보였다.

 

2. 우선 차례차례 봄, 여름, 가을, 겨울을 구현해보자.

 

봄에는 나무의 나이가 증가하며, 땅의 양분을 어린 나이의 나무부터 먹는다.

여름에는 죽은 나무의 나이의 1/2 만큼 양분이 더해진다.

가을에는 5의 배수인 경우, 나무가 8방향에 번식한다.

겨울에는 입력값만큼 땅에 양분을 더한다.

 

우선 Tree 라는 나무 클래스를 만들었다.

 

	static class Tree implements Comparable<Tree>{
		int x;
		int y;
		int age;
		
		Tree(int x, int y, int age){
			this.x = x;
			this.y = y;
			this.age =age;
		}

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

 

그리고 우선순위를 나이에 따라 오름차순으로 만들기 위해 Comparable을 사용하였다.

 

static PriorityQueue<Tree> trees = new PriorityQueue<Tree>();

우선순위 큐 trees라고 지정한 다음, 어린 나무들이 앞에 나타나도록 하였다.

 

그리고 봄에서 양분을 먹으면서 죽게 되는 나무가 나타나게 되면 해당 위치의 나무들은 다 죽게 된다.

따라서 바로 여름을 진행시켜서 시간을 단축시킨다. 또한 나무의 나이가 증가했을 때 5의 배수인지 확인을 해서 별도의 리스트에 5의 배수인 나무들을 넣어주고, 가을에서 해당 나무를 번식시킨다.

 

겨울은 단순 2중 for문을 통해서 땅에 양분을 넣도록 하였다.

 

 

전체 코드는 다음과 같다.