백준 16235번: 나무 재테크

문제 설명

• 주어진 조건대로 구현하는 문제입니다.

접근법

• 새로운 나무(age=1)를 lst의 앞으로 저장하면 자동으로 정렬된 효과를 얻을 수 있습니다.

pseudocode

main(){
    for(k번){
        SpringSummer();
        FallWinter();
    }
    점수계산 후 출력
}

SpringSummer(){
	dead_tree = 여름에 영양분이 될 나무 모음
	// 봄
	for(배열 전체를 탐색하면서){
    	if(해당 위치에 나무가 없으면) 패스
        for(리스트에 들어있는 순서대로 나무를 꺼내서){
        	if(나무가 먹을 영양분이 땅에 남아있다면){
            	영양분을 먹고 
                나무가 자람
            }else{ // 나무가 먹을 영양분이 없다면
            	여름에 영양분이 될 나무 리스트에 추가
            }
        }
    }
    for(dead_tree){
    	해당 나무의 위치에 age/2만큼의 양분을 더함
    }
}
FallWinter(){
	for(배열 전체를 탐색하면서){
    	// 겨울
        (i,j)에 입력으로 주어진 만큼의 양분을 추가합니다.
        // 가을
        for(나무들을 검사하면서){
        	if(나무의 나이가 5의 배수면){
            	주변 8곳에 나무를 심습니다.
            }
        }
        
    }
}

정답

import java.util.*;

public class Main {
	static int N,M,K;
	static int[][] AddFood,Earth;
	static LinkedList<Tree>[][] lst;
	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) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		AddFood = new int[N][N]; // 겨울에 기계가 추가하는 양분의 양

		Earth = new int[N][N]; // 현재 토지의 양분
		lst = new LinkedList[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				lst[i][j] = new LinkedList<Tree>();
			}
		}
		
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				AddFood[i][j] = sc.nextInt();
			}
			Arrays.fill(Earth[i], 5); // 현재 토지 초기화
		}
		

		
		// 입력으로 주어지는 나무
		for (int m = 0; m < M; m++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int age = sc.nextInt();
			lst[x-1][y-1].add(new Tree(x-1,y-1,age));
		}
		
		
		for (int k = 0; k < K; k++) {
			SpringSummer();
			FallWinter();
		}
		System.out.println(Score());
		
	}
	public static void SpringSummer() {
		List<Tree> dead_tree = new ArrayList<Tree>(); // 여름에 양분이 될 나무 모음

		// 봄
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int size = lst[i][j].size();
				if(size == 0) continue;
				// Collections.sort(lst[i][j], Collections.reverseOrder()); // age가 1인 나무를 addFirst한다면 내림차순 정렬을 할 필요가 없습니다.
				for (int t = 0; t < size; t++) {
					Tree val = lst[i][j].poll();
					if(val.age<=Earth[i][j]) {
						Earth[i][j] -= val.age;
						val.age++;
						lst[i][j].addLast(val);
					}else{
						// Earth[i][j]+=val.age/2; // 틀린 코드
							// 처음에 곧바로 양분을 Earth에 추가했더니 오답이 출력되었습니다. 
							// 곧바로 양분을 더하면 다음 나무에 영향을 받기 때문입니다.
							// 예제 테스트케이스의 마지막 문제가 85가 아닌 91이 나온다면 이러한 부분때문일 가능성이 큽니다.
						dead_tree.add(val);
					}
				}
			}
		}
		
		// 여름 - 영양분을 얻지 못한 나무를 모두 양분으로 만들어줍니다.
		int size = dead_tree.size();
		for (int i = 0; i < size; i++) {
			Tree val = dead_tree.get(i);
			Earth[val.x][val.y] += val.age/2;
		}
		
	}
	
	public static void FallWinter() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				// 겨울 - 가을에서 Earth가 활용되지 않기 때문에 먼저 갱신해도 상관 없습니다.
                // 먼저 갱신하는 이유는 가을에서 size가 0인 경우는 continue해 모든 (i,j)가 실행되지 않기 때문입니다.
				Earth[i][j] += AddFood[i][j];		

				// 가을 - 나이가 5의 배수인 나무가 증식합니다.
				int size = lst[i][j].size();
				if(size == 0) continue;
				for (int k = 0; k < size; k++) {
					Tree val = lst[i][j].get(k);
					if(val.age%5 == 0) {
						for (int d = 0; d < 8; d++) {
							int nx = i+dx[d];
							int ny = j+dy[d];
							if(0<= nx && nx < N && 0<= ny && ny <N) {
								lst[nx][ny].addFirst(new Tree(nx,ny,1)); // 새로생긴 나무를 lst의 앞에 추가시킴으로써 봄에 나이가 어린 나무가 우선적으로 양분을 섭취합니다.
							}
						}
					}
				}
				

			}
		}
	}
	
	// 최종 점수를 계산하는 메서드입니다.
    // 모든 땅을 돌면서 나무의 개수(lst[i][j].size())를 다 더합니다.
	public static int Score() {
		int score = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				score += lst[i][j].size();
			}
		}
		return score;
	}
	
	static class Tree implements Comparable<Tree>{
		int x;
		int y;
		int age;
		public Tree(int x, int y, int age) {
			super();
			this.x = x;
			this.y = y;
			this.age = age;
		}
		@Override
		public String toString() {
			return "Tree [x=" + x + ", y=" + y + ", age=" + age + "]";
		}
		@Override
		public int compareTo(Tree o) {
			// TODO Auto-generated method stub
			return o.age - this.age;
		}
		
	}
}

기타

• 유사문제 마법사-상어와-파이어볼