글 읽기 - 나무 재테크 시간초과

han03092 5년 전 0

자꾸 시간초과가 뜨는데 왜그런지 잘 모르겠어요 ㅠ
	import java.util.*;
	
	class tree implements Comparable{
		int age;
		int x, y;
		int isAlive;
		tree(int age, int x, int y){
			this.age = age;
			this.x = x;
			this.y = y;
			isAlive = 0;
		}
		
		public int compareTo(Object o) {
			tree t = (tree) o;
			return -this.age + t.age; 
		}
	}
	
	public class Main {
		

		static int n,m,k;
		static int map[][];
		static LinkedList <tree> t = new LinkedList <tree>();
		
		public static void main(String args[]) {
			
			Scanner scan = new Scanner(System.in);	
			n = scan.nextInt();
			m = scan.nextInt();
			k = scan.nextInt();
			map = new int [n+1][n+1];
			int S2D2[][] = new int [n+1][n+1];
			for(int i = 1; i<n+1; i++) {
				for(int j =1; j<n+1; j++) {
					S2D2[i][j] = scan.nextInt();
					map[i][j] = 5;
				}
			}
			
			for(int i =0; i<m ; i++) {
				int a,r,c;
				r = scan.nextInt();
				c = scan.nextInt();
				a = scan.nextInt();
				t.add(new tree(a,r,c));
			}
			
			Collections.sort(t);
			for(int i = 0; i<k; i++) {				
				for(int j = t.size()-1; j>=0; j--) {
					if(t.get(j).isAlive == 0) {
						if(t.get(j).age <= map[t.get(j).x][t.get(j).y]) {
							map[t.get(j).x][t.get(j).y] -= t.get(j).age;
							t.get(j).age++;
						}
						else {
							t.get(j).isAlive--;
						}
					}
				}
				//봄
				
				for(int j = t.size()-1; j>=0; j--)  {
					if(t.get(j).isAlive == -1) {
						t.get(j).isAlive --;
						map[t.get(j).x][t.get(j).y] += t.get(j).age/2;
						t.remove(t.get(j));
						j++;
					}
					
				}
				//여름
				
				for(int j = t.size()-1; j>=0; j--) {
					if((t.get(j).age % 5) == 0 && t.get(j).isAlive == 0) {
						breed(t.get(j));
					}
				}
				//가을
				
				for(int x =1; x<n+1; x++) {
					for(int y = 1 ; y<n+1 ;y++) {
						map[x][y] += S2D2[x][y];
					}
				}
			}
//			int result =0;
//			for(int i=0; i< t.size();i++) {
//				if(t.get(i).isAlive==0) result ++;
//			}
//			System.out.println(result);
			System.out.println(t.size());
			long end = System.currentTimeMillis();
		}
		
		static void breed(tree T) {
			if(T.x>1&& T.x<n) {
				if(T.y>1 && T.y<n) {
					t.add(new tree(1,T.x+1, T.y+1));
					t.add(new tree(1,T.x+1, T.y-1));
					t.add(new tree(1,T.x+1, T.y));
					t.add(new tree(1,T.x-1, T.y+1));
					t.add(new tree(1,T.x-1, T.y-1));
					t.add(new tree(1,T.x-1, T.y));
					t.add(new tree(1,T.x, T.y+1));
					t.add(new tree(1,T.x, T.y-1));
					//8칸
				}
				if(T.y == 1) {
					t.add(new tree(1,T.x+1, T.y+1));
					t.add(new tree(1,T.x+1, T.y));
					t.add(new tree(1,T.x-1, T.y+1));
					t.add(new tree(1,T.x-1, T.y));
					t.add(new tree(1,T.x, T.y+1));
				}
				if(T.y == n) {
					t.add(new tree(1,T.x+1, T.y-1));
					t.add(new tree(1,T.x+1, T.y));
					t.add(new tree(1,T.x-1, T.y-1));
					t.add(new tree(1,T.x-1, T.y));
					t.add(new tree(1,T.x, T.y-1));
				}
				//각각 다섯칸
			}
			if(T.x == 1) {
				if(T.y>1 && T.y<n) {
					t.add(new tree(1,T.x+1, T.y+1));
					t.add(new tree(1,T.x+1, T.y-1));
					t.add(new tree(1,T.x+1, T.y));
					t.add(new tree(1,T.x, T.y+1));
					t.add(new tree(1,T.x, T.y-1));
				}
				if(T.y == 1) {
					t.add(new tree(1,T.x+1, T.y+1));
					t.add(new tree(1,T.x+1, T.y));
					t.add(new tree(1,T.x, T.y+1));
				}
				if(T.y == n) {
					t.add(new tree(1,T.x+1, T.y-1));
					t.add(new tree(1,T.x+1, T.y));
					t.add(new tree(1,T.x, T.y-1));	
				}
			}
			if(T.x == n) {
				if(T.y>1 && T.y<n) {
					t.add(new tree(1,T.x-1, T.y+1));
					t.add(new tree(1,T.x-1, T.y-1));
					t.add(new tree(1,T.x-1, T.y));
					t.add(new tree(1,T.x, T.y+1));
					t.add(new tree(1,T.x, T.y-1));
				}
				if(T.y == 1) {
					t.add(new tree(1,T.x-1, T.y+1));
					t.add(new tree(1,T.x-1, T.y));
					t.add(new tree(1,T.x, T.y+1));
				}
				if(T.y == n) {
					t.add(new tree(1,T.x-1, T.y-1));
					t.add(new tree(1,T.x-1, T.y));
					t.add(new tree(1,T.x, T.y-1));
	
				}
			}
			
		}
	}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

나무 재테크 시간초과

han03092 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
