백준] 16235 나무 재테크
언어 : Java
풀이 방법 : 시뮬레이션
URL : https://www.acmicpc.net/problem/16235
16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든
www.acmicpc.net
간단한 문제 설명
N X N 의 이차원 배열에 나무를 심는데, 나무는 봄, 여름, 가을, 겨울에 따라 나이를 먹거나 죽거나 번식을 한다. 문제에 주어지는 조건에 대해 나무의 상태를 관리하는 문제이다.
풀이 과정
문제를 풀면서 다시 한번 깨달은 것은 'ArrayLsit'를 쓰자! 였다.
같은 코드인데 LinkedList로 구현한 코드는 시간초과가 나오고, ArrayList로 구현한 코드는 통과되었다. 이런 ArrayList만 가능한 문제를 예전에도 접한 적이 있는데, 이번 나무재테크를 풀면서 다시 한번 ArrayList를 써야한다는 걸 확신하게 되었다.
|
1
2
3
4
5
6
7
8
9
10
11
|
static class Info{
int nowNutrient; // 현재있는 양분
int plusNutrient; // 추가되는 양분
ArrayList<Integer> treeAge;
public Info(int plus, ArrayList<Integer> treeAge) {
this.nowNutrient = 5;
this.plusNutrient = plus;
this.treeAge = treeAge;
}
}
|
한 칸에 관리해야 할 상태(현재 양분, 추가되어야할 양분, 나무)가 여러개라 N X N의 2차원 배열의 각 칸을 Info라는 클래스의 배열로 선언했다. ( Info[][] map = new Info[N][N]; )
나무를 관리하는 방식을 두 가지 방식으로 풀어봤다.
1. 각 칸의 나무를 관리하는 ArrayList를 나무의 나이만 관리하는 방식
2. 각 칸의 나무를 관리하는 ArrayList를 나무의 나이와 갯수까지 관리하는 방식
둘 다 통과가 되었고, 둘 다 LinkedList면 시간 초과가 난다.
구현하면서 봄과 여름을 묶어서 구현할 수 있고, 가을과 겨울을 묶어서 구현할 수 있어서 springAndSummer메소드와 fallAndWinter메소드를 만들었다.
* 디버깅은 현재 양분과 현재 나무의 갯수, 나무의 나이를 봄/여름, 가을/겨울이 끝날 때마다 따로따로 출력하면서 디버깅했다.
소스코드
1. 나무의 나이만 관리하는 방식
|
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
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 Main_16235_나무재테크 {
static class Info{
int nowNutrient; // 현재 있는 양분
int plusNutrient; // 추가되는 양분
ArrayList<Integer> treeAge;
public Info(int plus, ArrayList<Integer> treeAge) {
this.nowNutrient = 5;
this.plusNutrient = plus;
this.treeAge = treeAge;
}
}
private static Info[][] map;
private static int N;
private static int nutrient;
private static int ans;
private static int[] dr = { -1,-1,-1,1,1,1,0,0 };
private static int[] dc = { -1,0,1,1,0,-1,1,-1 };
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken()); // N X N 크기의 땅
int M = Integer.parseInt(st.nextToken()); // 구매한 나무의 수
int K = Integer.parseInt(st.nextToken()); // K년
map = new Info[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine());
for (int j = 0, index = 0; j < N; j++, index += 2) {
int plus = Integer.parseInt(st.nextToken());
map[i][j] = new Info(plus, new ArrayList<>());
}
}
// x y z => x y 나무의 위치 z 나무의 나이
for (int i = 0; i < M; i++) {
st = new StringTokenizer(in.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int age = Integer.parseInt(st.nextToken());
map[x - 1][y - 1].treeAge.add(age);
ans++;
}
// --------------------------- 입력부
for (int i = 0; i < K; i++) {
springAndSummer();
fallAndWinter();
}
System.out.println(ans);
}
private static void fallAndWinter() {
// 나무가 번식한다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
Info current = map[i][j];
for (int k = size - 1; k >= 0; k--) {
//번식하는 나무의 나이는 5의 배수
for (int d = 0; d < 8; d++) {
int nr = i + dr[d];
int nc = j + dc[d];
if(nr >= 0 && nc >= 0 && nr < N && nc < N) {
map[nr][nc].treeAge.add(1); // 나이가 1인 나무가 생긴다.
ans++;
}
}
}
}
// winter
current.nowNutrient += current.plusNutrient;
}
}
// System.out.println("가을, 겨울 끝");
// print1();
// print2();
// print3();
}
private static void springAndSummer() {
// 봄엔 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.
// 하나의 칸에 여러 나무가 있다면 나이가 어린 나무부터 양분을 먹는다.
// 만약, 땅에 양분이 부족해 자신의 나이만큼 먹을 수 없는 나무는 즉시 죽는다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
Info current = map[i][j];
for (int k = size - 1; k >= 0; k--) {
// 양분 충분하면
}else {
// 양분이 부족하면 나무는 죽는다..
ans--;
}
}
// summer
current.nowNutrient += nutrient;
nutrient = 0;
}
}
// System.out.println("봄, 여름 끝");
// print1();
// print2();
// print3();
}
private static void print1() {
System.out.println("현재 양분");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(map[i][j].nowNutrient);
}
System.out.println();
}
}
private static void print2() {
System.out.println("현재 나무 갯수");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
}
System.out.println();
}
}
private static void print3() {
System.out.println("현재 나무 나이");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < size; k++) {
}
System.out.print(" ");
}
System.out.println();
}
}
}
|
2. 나무의 나이와 갯수까지 관리하는 방식
|
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
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 Main_16235_나무재테크2 {
static class Info{
int nowNutrient; // 현재 있는 양분
int plusNutrient; // 추가되는 양분
ArrayList<Tree> trees;
public Info(int plus, ArrayList<Tree> treeAge) {
this.nowNutrient = 5;
this.plusNutrient = plus;
this.trees = treeAge;
}
}
static class Tree{
int age;
int cnt;
public Tree(int age, int cnt) {
this.age = age;
this.cnt = cnt;
}
}
private static Info[][] map;
private static int N;
private static int nutrient;
private static int ans;
private static int[] dr = { -1,-1,-1,1,1,1,0,0 };
private static int[] dc = { -1,0,1,1,0,-1,1,-1 };
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken()); // N X N 크기의 땅
int M = Integer.parseInt(st.nextToken()); // 구매한 나무의 수
int K = Integer.parseInt(st.nextToken()); // K년
map = new Info[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine());
for (int j = 0, index = 0; j < N; j++, index += 2) {
int plus = Integer.parseInt(st.nextToken());
map[i][j] = new Info(plus, new ArrayList<>());
}
}
// x y z => x y 나무의 위치 z 나무의 나이
for (int i = 0; i < M; i++) {
st = new StringTokenizer(in.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int age = Integer.parseInt(st.nextToken());
map[x - 1][y - 1].trees.add(new Tree(age, 1));
ans++;
}
// --------------------------- 입력부
for (int i = 0; i < K; i++) {
springAndSummer();
fallAndWinter();
}
System.out.println(ans);
}
private static void fallAndWinter() {
// 나무가 번식한다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
Info current = map[i][j];
for (int k = size - 1; k >= 0; k--) {
//번식하는 나무의 나이는 5의 배수
for (int d = 0; d < 8; d++) {
int nr = i + dr[d];
int nc = j + dc[d];
if(nr >= 0 && nc >= 0 && nr < N && nc < N) {
}
}
}
}
// winter
current.nowNutrient += current.plusNutrient;
}
}
// System.out.println("가을, 겨울 끝");
// print1();
// print2();
// print3();
}
private static void springAndSummer() {
// 봄엔 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.
// 하나의 칸에 여러 나무가 있다면 나이가 어린 나무부터 양분을 먹는다.
// 만약, 땅에 양분이 부족해 자신의 나이만큼 먹을 수 없는 나무는 즉시 죽는다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
Info current = map[i][j];
for (int k = size - 1; k >= 0; k--) {
Tree tree = current.trees.get(k);
// 양분 충분하면
}else {
// 양분이 부족하면 나무는 죽는다.
// 몇개의 나무까지 커버 가능한지 확인
if(saveNum == 0)
else
ans -= dieNum;
}
}
// summer
current.nowNutrient += nutrient;
nutrient = 0;
}
}
// System.out.println("봄, 여름 끝");
// print1();
// print2();
// print3();
}
private static void print1() {
System.out.println("현재 양분");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(map[i][j].nowNutrient);
}
System.out.println();
}
}
private static void print2() {
System.out.println("현재 나무 갯수");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
}
System.out.println();
}
}
private static void print3() {
System.out.println("현재 나무 나이");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < size; k++) {
}
System.out.print(" ");
}
System.out.println();
}
}
}
|
'개발 > 알고리즘 풀이' 카테고리의 다른 글
| 코딩테스트] 코딩테스트가 처음이라면? 혹은 오랜만이라면? 간단 로드맵 (9) | 2021.03.03 |
|---|---|
| 백준] 15486 퇴사2 ( DP/ Java ) (0) | 2020.02.27 |
| 백준] 14501 퇴사 (완전탐색으로 풀기 / Java) (1) | 2020.02.26 |
| 프로그래머스] 가장 큰 정사각형 찾기 (Java) (0) | 2020.02.10 |
| SW Expert Academy] 1249 D4 보급로 (0) | 2020.02.01 |