https://www.acmicpc.net/problem/16235
16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터
www.acmicpc.net
풀이 방법
사계절마다 수행하는 작업을 잘 읽고 따라서 구현만 하면 되는 문제이지만 시간 복잡도를 만족하는 것이 관건이다. 시간 제한을 만족하기 위해 시간 복잡도를 크게 감소시켜야 하는 부분은 두 부분이 있었다.
1. 나이가 어린 순대로 순회하여 양분을 먹기 위해서 나이가 1인 나무를 리스트의 맨 앞에 추가해줄 때
2. 죽은 나무들을 제거할 때
1번에서 자료 구조 List를 사용한다면 요소를 맨 앞에 추가할 때 O(n) 이 걸려 for문을 돌릴 경우 O(n^2) 이므로 시간복잡도가 커진다. 따라서, 이를 해결하기 위해 자료 구조를 덱을 사용한다. 덱은 양방향 추가가 가능하므로 O(1) 이 걸린다.
2번의 경우 죽은 나무들을 기존 덱 상태에서 remove 메소드를 사용하여 제거하는 방법을 선택하면 O(n) 이 걸린다. 따라서, remove 를 사용하지 않고 죽은 나무를 구분해줄 방법을 생각했다. 살아 있는 나무를 넣어줄 덱 next 와 죽은 나무를 넣어줄 리스트 dead 를 선언하여 각각 해당하는 경우에 따라 나무들을 삽입한 뒤, 죽은 나무들은 순회하며 땅의 양분을 갱신하고 next 는 다음 덱 상태로 갱신하도록 하였다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static class Tree {
int x;
int y;
int z; // 나이
public Tree(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
// 나이 1 증가
public void increase() {
this.z += 1;
}
}
static int N, M, K;
static int[][] A; // 각 칸에 추가될 양분
static int[][] board; // 땅 상태
static Deque<Tree> trees = new LinkedList<>();
static int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};
static int[] dy = {-1, 1, 0, 0, -1, 1, 1, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
N = Integer.parseInt(line[0]);
M = Integer.parseInt(line[1]);
K = Integer.parseInt(line[2]);
A = new int[N][N];
board = new int[N][N];
// 처음 양분을 5로 초기화
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
board[i][j] = 5;
}
}
// A배열 입력
for(int i=0; i<N; i++) {
line = br.readLine().split(" ");
for(int j=0; j<N; j++) {
A[i][j] = Integer.parseInt(line[j]);
}
}
// 나무 정보 입력
for(int i=0; i<M; i++) {
line = br.readLine().split(" ");
int x = Integer.parseInt(line[0])-1;
int y = Integer.parseInt(line[1])-1;
int z = Integer.parseInt(line[2]);
trees.add(new Tree(x, y, z));
}
// K년 동안의 상태 갱신
int t = 0;
while(t < K) {
// 봄, 여름, 양분 먹기
eat();
// 가을, 번식
reproduce();
// 겨울, 로봇
addNutrient();
t++;
}
System.out.println(trees.size());
}
public static void eat() {
Deque<Tree> next = new LinkedList<>(); // 살아 있는 나무
List<Tree> dead = new ArrayList<>(); // 죽은 나무
// 자신의 나이만큼 양분 먹고 나이 1 증가하기
for(Tree tree : trees) {
// 양분이 나이 이상이면 양분을 나이만큼 양분 먹음
if(board[tree.x][tree.y] >= tree.z) {
board[tree.x][tree.y] -= tree.z; // 나이만큼 감소
tree.increase(); // 나이 증가
next.addLast(tree);
} else {
dead.add(tree);
}
}
// 죽은 나무의 나이를 2로 나눈 만큼 해당 칸의 양분 추가
for(int i=0; i<dead.size(); i++) {
Tree tree = dead.get(i);
board[tree.x][tree.y] += tree.z / 2;
}
trees = next; // 살아 있는 나무들을 갱신
}
// 번식
public static void reproduce() {
List<Tree> newTrees = new ArrayList<>(); // 새로 생기는 나무
for(Tree tree : trees) {
int age = tree.z; // 나이
int x = tree.x;
int y = tree.y;
if(age > 0 && age % 5 == 0) { // 5의 배수이면
for(int j=0; j<8; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if(nx < 0 || nx >= N || ny < 0 || ny >= N) {
continue;
}
newTrees.add(new Tree(nx, ny, 1));
}
}
}
for(int i=0; i<newTrees.size(); i++) {
trees.addFirst(newTrees.get(i));
}
}
// 로봇이 땅에 양분 추가
public static void addNutrient() {
// 양분 추가
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
board[i][j] += A[i][j];
}
}
}
}'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 19236 청소년 상어 자바(java) (1) | 2023.12.20 |
|---|---|
| 백준 14889 스타트와 링크 자바(java) (1) | 2023.12.19 |
| 백준 1182 부분수열의 합 자바(java) (0) | 2023.12.05 |
| 백준 13335 트럭 자바(java) (0) | 2023.11.18 |
| 백준 1360 되돌리기 자바(java) (0) | 2023.11.17 |