[BaekJoon] 19539 사과나무 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/19539

2.  문제

요약

• 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 1번부터 N번까지 심었고 나무들의 초기 높이는 모두 0입니다.
• 물뿌리개 2개를 준비했는데, 한 물뿌리개는 나무 하나를 1만큼 성장시키고, 다른 물뿌리개는 나무 하나를 2만큼 성장시킵니다.
• 두 물뿌리개는 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에는 사용할 수 없으며 두 물뿌리개를 한 나무에 사용하여 3만큼 키울 수도 있습니다.
• 갊자가 각 사과나무의 높이가 이런 배치가 되었으면 좋겠다는 배치를 주었는데, 해당 배치를 만들 수 있는지 여부를 판단하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 자연수인 뒷뜰에 심은 사과나무의 개수 N이 주어지고 두 번째 줄에 0보다 크거나 같고 10,000보다 작거나 같은 N개의 정수인 갊자가 바라는 i번째 나무의 높이인 $h_i$들이 주어집니다.
• 출력: 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있다면 "YES"를, 아니면 "NO"를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public String isPossible(int[] heights) {
		int total_height = 0;
		int odd = 0;
		for(int i = 0; i < heights.length; i++) {
			total_height += heights[i];
			if(heights[i] % 2 == 1) {
				odd++;
			}
		}
		if(total_height % 3 == 0 && odd <= total_height / 3) {
			return "YES";
		} else {
			return "NO";
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		int[] heights = new int[num];
		String[] input = br.readLine().split(" ");
		br.close();
		for(int i = 0; i < num; i++) {
			heights[i] = Integer.parseInt(input[i]);
		}
		Main m = new Main();
		bw.write(m.isPossible(heights) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 주어진 사과나무 높이의 합은 한 번에 총 3만큼 성장시키기 때문에 3의 배수가 됩니다.
• 주어진 사과나무 높이의 합을 3으로 나눈다면 총 걸리는 일수가 나오게 됩니다. 이 수는 또한 1만큼 자라게 하는 물뿌리개와 2만큼 자라게 하는 물뿌리개가 사용되는 횟수를 의미하기도 합니다.
• 홀수 높이의 사과나무는 2만큼 성장시키는 물뿌리개로는 성장시킬 수 없기 때문에 홀수 높이의 사과나무 개수를 셉니다.
• 만약 이 개수가 물뿌리개를 사용하는 총 일수를 초과한다면 해당 높이들을 맞출 수 없습니다.
• 그렇기 때문에 만약 사과나무 높이의 합이 3의 배수이고 홀수 높이의 사과나무의 개수가 물뿌리개를 사용하는 총 일수보다 작거나 같다면 YES를 출력하고 그렇지 않다면 NO를 출력합니다.