16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터
www.acmicpc.net
- 풀이
문제 설명대로 봄, 여름, 가을, 겨울에 해야될 일들을 메소드로 나누어서 풀었다.
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.InputMismatchException;
public class Main {
static int N, M, K;
static int[][] array, foodForTree;
static ArrayList<Tree> tree;
static ArrayList<Tree> livedTree;
static ArrayList<Tree> deadTree;
static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };
public static void main(String[] args) throws Exception {
SetData();
System.out.println(tree.size());
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
K = in.nextInt();
array = new int[N + 1][N + 1];
tree = new ArrayList<>();
foodForTree = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
foodForTree[i][j] = in.nextInt();
array[i][j] = 5;
}
}
for(int i = 0; i < M; i++)
tree.add(new Tree(in.nextInt(), in.nextInt(), in.nextInt()));
Solve();
}
private static void Solve() {
while (K-- > 0) {
livedTree = new ArrayList<>();
deadTree = new ArrayList<>();
Collections.sort(tree); // 정렬
ComeSpring();
ComeSummer();
ComeFall();
ComeWinter();
}
}
private static void ComeSpring() {
for (int i = 0; i < tree.size(); i++) {
Tree t = tree.get(i);
// 양분이 충분한 경우 양분을 먹는다.
if(array[t.x][t.y] >= t.age) {
array[t.x][t.y] -= t.age;
t.age++;
livedTree.add(t);
} else {
// 그렇지 못한 경우 죽음
deadTree.add(t);
}
}
tree.clear();
tree.addAll(livedTree);
}
private static void ComeSummer() {
// 죽은 나무 양분
for (int i = 0; i < deadTree.size(); i++) {
Tree t = deadTree.get(i);
array[t.x][t.y] += t.age / 2;
}
}
private static void ComeFall() {
for (int i = 0; i < tree.size(); i++) {
if(tree.get(i).age % 5 != 0) continue;
int x = tree.get(i).x;
int y = tree.get(i).y;
for(int direction = 0; direction < 8; direction++) {
int r = x + dx[direction];
int c = y + dy[direction];
if(r <= 0 || c <= 0 || r > N || c > N) continue;
tree.add(new Tree(r, c, 1));
}
}
}
private static void ComeWinter() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
array[i][j] += foodForTree[i][j];
}
}
}
}
class Tree implements Comparable<Tree>{
int x;
int y;
int age;
public Tree(int x, int y, int age) {
this.x = x;
this.y = y;
this.age = age;
}
@Override
public int compareTo(Tree t) {
return this.age - t.age;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
- 시간초과 났던 코드
달라진점 : queue 부분을 arraylist로 고쳐줌
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N, M, K;
static int[][] array, foodForTree;
static ArrayList<Tree> tree;
static Queue<Tree> diedTree;
static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };
public static void main(String[] args) throws Exception {
SetData();
System.out.println(tree.size());
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
K = in.nextInt();
array = new int[N + 1][N + 1];
tree = new ArrayList<>();
diedTree = new LinkedList<>();
foodForTree = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
foodForTree[i][j] = in.nextInt();
array[i][j] = 5;
}
}
for(int i = 0; i < M; i++)
tree.add(new Tree(in.nextInt(), in.nextInt(), in.nextInt()));
Solve();
}
private static void Solve() {
while (K-- > 0) {
Collections.sort(tree); // 정렬
ComeSpring();
ComeSummer();
ComeFall();
ComeWinter();
}
}
private static void ComeSpring() {
for (int i = 0; i < tree.size(); i++) {
int x = tree.get(i).x;
int y = tree.get(i).y;
int age = tree.get(i).age;
// 양분이 충분한 경우 양분을 먹는다.
if(array[x][y] >= age) {
array[x][y] -= age;
tree.get(i).age++;
} else {
// 그렇지 못한 경우 죽음
diedTree.add(new Tree(x,y,age));
tree.remove(i);
i--;
}
}
}
private static void ComeSummer() {
// 죽은 나무가 양분으로 변함
while(!diedTree.isEmpty()) {
Tree temp = diedTree.poll();
array[temp.x][temp.y] += temp.age /2;
}
}
private static void ComeFall() {
for (int i = 0; i < tree.size(); i++) {
if(tree.get(i).age % 5 != 0) continue;
int x = tree.get(i).x;
int y = tree.get(i).y;
for(int direction = 0; direction < 8; direction++) {
int r = x + dx[direction];
int c = y + dy[direction];
if(r <= 0 || c <= 0 || r > N || c > N) continue;
tree.add(new Tree(r, c, 1));
}
}
}
private static void ComeWinter() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
array[i][j] += foodForTree[i][j];
}
}
}
}
class Tree implements Comparable<Tree>{
int x;
int y;
int age;
public Tree(int x, int y, int age) {
this.x = x;
this.y = y;
this.age = age;
}
@Override
public int compareTo(Tree t) {
return this.age - t.age;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
- 런타임 에러떳던 코드 (IllegalArgument)
런타임 에러 도움말
C/C++ (gcc) 언어: C99, C11, C90, C2x, C++98, C++11, C++14, C++17, C++20 런타임 에러 이유설명AssertionFailedassert함수가 실패SegfaultSegmentation faultBusErrorBus errorInvalidPointermunmap_chunk(): invalid pointerOutOfBounds컨테이너 또
www.acmicpc.net
return 0부분이 잘못되었다고하는데 잘 모르겠다..
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
static int N, M, K;
static int[][] array, foodForTree;
static ArrayList<Tree> tree;
static Queue<int []> diedTree;
static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };
public static void main(String[] args) throws Exception {
SetData();
System.out.println(tree.size());
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
K = in.nextInt();
array = new int[N + 1][N + 1];
tree = new ArrayList<>();
diedTree = new LinkedList<>();
foodForTree = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
foodForTree[i][j] = in.nextInt();
array[i][j] = 5;
}
}
for(int i = 0; i < M; i++)
tree.add(new Tree(in.nextInt(), in.nextInt(), in.nextInt()));
Solve();
}
private static void Solve() {
while (K-- > 0) {
Collections.sort(tree, new TreeCompare()); // 정렬
ComeSpring();
ComeSummer();
ComeFall();
ComeWinter();
}
}
private static void ComeSpring() {
for (int i = 0; i < tree.size(); i++) {
int x = tree.get(i).x;
int y = tree.get(i).y;
int age = tree.get(i).age;
// 양분이 충분한 경우 양분을 먹는다.
if(array[x][y] >= age) {
array[x][y] -= age;
tree.get(i).age++;
} else {
// 그렇지 못한 경우 죽음
diedTree.add(new int[] {x,y,age});
tree.remove(i);
i--;
}
}
}
private static void ComeSummer() {
// 죽은 나무가 양분으로 변함
while(!diedTree.isEmpty()) {
int[] temp = diedTree.poll();
array[temp[0]][temp[1]] += temp[2] /2;
}
}
private static void ComeFall() {
for (int i = 0; i < tree.size(); i++) {
if(tree.get(i).age % 5 != 0) continue;
int x = tree.get(i).x;
int y = tree.get(i).y;
int age = tree.get(i).age;
for(int direction = 0; direction < 8; direction++) {
int r = x + dx[direction];
int c = y + dy[direction];
if(r <= 0 || c <= 0 || r > N || c > N) continue;
tree.add(new Tree(r, c, 1));
}
}
}
private static void ComeWinter() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
array[i][j] += foodForTree[i][j];
}
}
}
}
class Tree{
int x;
int y;
int age;
public Tree(int x, int y, int age) {
this.x = x;
this.y = y;
this.age = age;
}
}
class TreeCompare implements Comparator<Tree> {
int ret = 0;
@Override
public int compare(Tree t1, Tree t2) {
if (t1.x == t2.x && t1.y == t2.y) {
if (t1.age < t2.age) {
ret = -1;
} else
ret = 1;
}
return ret;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 17143번 : 낚시왕 (0) | 2021.04.20 |
|---|---|
| [BOJ/JAVA] 백준 16236번 : 아기 상어 (0) | 2021.04.18 |
| [BOJ/JAVA] 백준 16234번 : 인구 이동 (0) | 2021.04.17 |
| [BOJ/JAVA] 백준 14499번 : 주사위 굴리기 (0) | 2021.04.16 |
| [BOJ/JAVA] 백준 14891번 : 톱니바퀴 (0) | 2021.04.15 |