카테고리 없음
백준 16235 - 나무재테크 (java)
jin_j_i_n
2021. 4. 18. 15:23
16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터
www.acmicpc.net
시뮬레이션 문제야 뭐 시키는대로 하면 된다지만 시간초과 걸렸었다
어린나무부터 양분을 소모하기 위해 priority 큐를 사용했는데 , 이 우선순위큐가 원소를 넣을때마다 내부적으로 정렬이 일어나기 떄문에 시간초과가 걸렸던 것 같다.
질문게시판을 참고해서 우선순위큐를 쓰지 않고 List를 써서 나무가 양분을 먹기 이전에만 한번 정렬을 해주었다.
우선순위큐를 쓸 때는 시간관련해서 신경을 좀 써줘야할것같다.
+ 추가, 삭제 연산이 더 빠른 ArrayList로도 바꿔서 해봤지만 똑같이 시간초과가 걸렸다.
추가 ,삭제보단 조회에서 시간이 더 걸려서 그런걸까?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
import java.io.*;
import java.util.*;
public class B1635 {
static int N;
static int K;
static int[][] food;
static int[][] add;
static int[] dx = {-1,-1,-1,0,0,1,1,1};
static int[] dy = {-1,0,1,-1,1,-1,0,1};
static List<Integer>[][] trees;
public static boolean check(int x, int y) {
return (x>=0 && y >= 0 && x < N && y < N);
}
public static void grow(int k) {
if( k >= K )return;
else {
//1. 봄 - 나무가 자신의 나이만큼 양분을 먹는다
for(int i=0; i<N; i++) {
for(int j=0 ; j < N; j++) {
Collections.sort(trees[i][j]);
List<Integer> tmp = new LinkedList<>();
int diedTree = 0;
while(!trees[i][j].isEmpty()) {
int age = trees[i][j].remove(0);
if(food[i][j] < age ) {
//나이만큼 양분이 없을때 , 이 이후의 나무는 양분을 먹지 못하고 죽는다
diedTree += age / 2;
while(!trees[i][j].isEmpty()) {
diedTree += trees[i][j].remove(0) / 2;
}
}else{
//자신의 나이만큼 양분을 먹는다 , 양분을 먹은 나무는 나이 1씩 증가
food[i][j] -= age;
tmp.add(age+1);
}
}
trees[i][j] = tmp;
// 2. 여름 - 죽은 나무가 양분으로 추가된다.
food[i][j] += diedTree;
}
}
for(int i=0 ; i<N; i++) {
for(int j=0 ; j<N; j++) {
// 3. 가을 - 나무가 번식한다, 5배수의 나무만 번식하고
// 인접한 8칸에 나이가 1인 나무가 생긴다.
List<Integer> tmp = new LinkedList<>();
while(!trees[i][j].isEmpty()) {
int tree = trees[i][j].remove(0);
if(tree % 5 == 0) {
for(int l =0 ; l<8 ; l++) {
int nx = i + dx[l];
int ny = j + dy[l];
if(check(nx, ny)){
trees[nx][ny].add(1);
}
}
}
tmp.add(tree);
}
trees[i][j] = tmp;
//4. 겨울 - 양분 추가
food[i][j] += add[i][j];
}
}
grow(k+1);
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
N = Integer.parseInt(inputs[0]);
int M = Integer.parseInt(inputs[1]);
K = Integer.parseInt(inputs[2]);
food = new int[N][N];
add = new int[N][N];
trees = new LinkedList[N][N];
for(int i=0 ; i<N ; i++) {
inputs = br.readLine().split(" ");
for(int j=0 ; j<N ; j++) {
trees[i][j] = new LinkedList<>();
add[i][j] = Integer.parseInt(inputs[j]);
food[i][j] = 5;
}
}
for(int i=0 ; i<M; i++ ) {
inputs = br.readLine().split(" ");
int a = Integer.parseInt(inputs[0]);
int b = Integer.parseInt(inputs[1]);
int tree = Integer.parseInt(inputs[2]);
trees[a-1][b-1].add(tree);
}
grow(0);
int count = 0;
for(int i=0 ; i<N ; i++) {
for(int j=0 ; j<N ; j++) {
count += trees[i][j].size();
}
}
System.out.println(count);
}
}
|
cs |