[SWEA]14510번:나무 높이(JAVA)

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do

 

---

• 풀이 방법[알고리즘]

그리디로 푸는 문제! 처음에 멋모르고 물을 주는 경우, 안주는 경우를 각각 구해서 완전 탐색으로 풀었다가 시간초과가 났다.

나무별로 더 커야 하는 값을 tree배열에 주고, tree의 값이 모두 0이 될 때까지 반복문을 수행한다. tree별로 값이 3이상이 남았을 경우엔 홀수에 1만큼, 짝수에 2만큼 자라게 표시해준다. 그리고 자라야 하는 값이 1이나 2가 남았을 경우엔 day확인해서 계산해준다.

sort를 빼먹으면 값이 다르게 나온다. 작은 값부터 처리해줘야 1,2를 제대로 계산하는 듯하다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			sb.append("#").append(tc).append(" ");
//			System.out.println(sb);
			int N = Integer.parseInt(br.readLine());
			int[] tree = new int[N];
			int limit = 0;
			int sum = 0;
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < tree.length; i++) {
				tree[i] = Integer.parseInt(st.nextToken());
				limit = Math.max(limit, tree[i]);
			}

			for (int i = 0; i < tree.length; i++) {
				tree[i] = limit - tree[i];
				sum += tree[i];
			}

			if (sum == 0) {
				sb.append(0).append("\n");
				continue;
			}

			Arrays.sort(tree);
			int day = 1;
			while (true) {
				for (int i = 0; i < tree.length; i++) {
					if (tree[i] >= 3) {
						if (day % 2 == 1) {
							tree[i] -= 1;
						} else {
							tree[i] -= 2;
						}
						break;
					}
					if (day % 2 == 1 && tree[i] == 1) {
						tree[i] = 0;
						break;
					}
					if (day % 2 == 0 && tree[i] == 2) {
						tree[i] = 0;
						break;
					}
				} // for
				if (check(tree))
					break;
				day++;
			} // while
			sb.append(day).append("\n");
		} // for_tc
		System.out.println(sb);
	}// main

	private static boolean check(int[] tree) {
		for (int i = 0; i < tree.length; i++) {
			if (tree[i] != 0)
				return false;
		}
		return true;
	}
}// class