BOJ 19539 - 사과나무

문제 링크

문제#

이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 $1$번부터 $N$번까지 심었다. 이 나무들의 초기 높이는 모두 $0$이다.

사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 $2$개를 준비했다. 한 물뿌리개는 나무 하나를 $1$만큼 성장시키고, 다른 물뿌리개는 나무 하나를 $2$만큼 성장시킨다. 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다. 두 물뿌리개를 한 나무에 사용하여 $3$만큼 키울 수도 있다.

물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다. 그 순간, 갊자가 놀러와서 각 사과나무의 높이가 이런 배치가 되었으면 좋겠다고 말했다. 이제 이하는 약간 걱정이 되기 시작했는데, 갊자가 알려준 사과나무의 배치를 이 프로그램 상으로 만들어내지 못할 수도 있기 때문이다.

이하는 이제 프로그램을 다시 수정하느라 바쁘기 때문에, 두 물뿌리개를 이용해 갊자가 알려준 사과나무의 배치를 만들 수 있는지의 여부를 판단하는 과정은 여러분의 몫이 되었다.

입력#

첫 번째 줄에는 자연수 $N$이 주어진다. $(1 \le N \le 100{,}000)$ 이는 이하가 뒷뜰에 심은 사과나무의 개수를 뜻한다.

두 번째 줄에는 $N$개의 정수 $h_1, h_2, \cdots, h_N$이 공백으로 구분되어 주어진다. $(0 \le h_i \le 10{,}000)$ $h_i$는 갊자가 바라는 $i$번째 나무의 높이이다.

출력#

첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다.

풀이#

하루에 한 나무는 1만큼, 다른 나무는 2만큼 자라므로 하루 전체 증가량은 항상 3이다. 따라서 전체 높이 합이 3의 배수가 아니면 목표를 만들 수 없다.

또 하나 봐야 할 점은 1만큼 물을 줘야 하는 횟수다. 각 나무의 높이를 2로 나누면 2짜리 물주기를 몇 번 쓸 수 있는지 알 수 있고, 홀수 높이의 개수는 반드시 1짜리 물주기가 필요한 횟수다.

코드에서는 전체 합 sum, 홀수 개수 cntOne, 2짜리 물주기 가능 횟수 cntTwo를 센다. sum % 3 == 0이고 cntOne <= cntTwo이면 1짜리 물주기를 2짜리 물주기와 짝지을 수 있으므로 가능하다.

코드#

import java.io.*;
import java.util.*;
 
public class Main {
		
	static int[] arr;
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
 
		System.out.println(solve());
	}
	
	static String solve() {
		int sum = 0;
		int cntOne = 0, cntTwo = 0;
		
		for (int num : arr) {
			sum += num;
			cntOne += num % 2;
			cntTwo += num / 2;
		}
		
		if (sum % 3 != 0) return "NO";
		else if (cntOne > cntTwo) return "NO";
		return "YES";
	}
	
}

복잡도#

• 시간 복잡도: 나무를 한 번 훑으므로 $O(N)$이다.
• 공간 복잡도: 입력 배열 외에는 상수 공간만 사용하므로 $O(1)$이다.

마무리#

사과나무는 전체 합과 홀수 높이만 보면 된다. 물주기 조합을 직접 시뮬레이션할 필요는 없다.