[백준/JAVA] 19539 - 사과나무

[문제 포인트]

+1물뿌리개와 +2물뿌리개는 무조건 동시에 사용되어야 함 

=> " 전체 기대 높이의 합이 3의 배수 "여야!! (∵한 번 물 뿌리면 총 높이 +3 증가)

 

물을 뿌린 횟수(전체 기대 높이의 합 / 3) = +1물뿌리개를 뿌린 횟수 = +2물뿌리개를 뿌린 횟수

 

 일단 +2물뿌리개를 최대로 사용 하도록 하자!!

=> +2물뿌리개를 사용해야하는 횟수에서 1개를 빼서, +1물뿌리개를 사용해야하는 횟수에 2개를 더해주면, 균형 맞출 수 O?!

+1물뿌리개를 반드시 사용해야하는 횟수 ≤ +2물뿌리개를 사용할수도 있는 횟수

1) 기대 높이가 홀수일 경우 : +1물뿌리개를 무조건 1번 사용해야함.
나머지를 절반으로 나눈( /2)만큼은 +2물뿌리개 사용 가능
2) 기대 높이가 짝수일 경우 : 기대높이를 절반으로 나눈( /2)만큼 +2물뿌리개 사용 가능

 

[문제 풀이]

- 내코드

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
	int n = Integer.parseInt(br.readLine()); // 사과나무의 수
		
	int cnt1 = 0; // +1물뿌리개를 반드시 사용해야되는 횟수
	int cnt2 = 0; // +2물뿌리개를 사용할수도 있는 횟수
		
	int sum = 0; // 총 기대높이들의 합
	StringTokenizer st = new StringTokenizer(br.readLine());
	for(int i=0; i<n; i++) {
		int num = Integer.parseInt(st.nextToken());
		if(num%2 == 1) { // 기대높이가 홀수일 경우에는
			cnt1 += 1; // +1물뿌리개를 무조건 1번 사용해야!!
			cnt2 += num/2; // +2물뿌리개를 기대높이를 절반으로 나눈만큼(/2) 사용 가능
		}
		else {// 기대높이가 짝수일 경우에는
			cnt2 += num/2; // +2물뿌리개를 기대높이를 절반으로 나눈만큼(/2) 사용 가능
		}
		sum += num; // 총 기대높이들의 합 업데이트
	}
	if(sum%3 != 0) { // 전체 기대 높이의 합이 3의 배수가 아니라면 => 불가능!!
		System.out.println("NO");
	}
	else if(sum%3 == 0 && cnt1 == cnt2) { // 전체 기대높이의 합이 3의 배수이고, +1물뿌리개수 = +2물뿌리개수라면 => 가능!!
		System.out.println("YES");
	}
	else if(sum%3 == 0 && cnt1 < cnt2) { // 전체 기대높이의 합이 3의 배수이고, +1물뿌리개수 < +2물뿌리개수라면 => 가능성 있음!!
		while(true) {
			cnt1 += 2; // +1물뿌리개 수 2 증가
			cnt2 -= 1; // +2물뿌리개 수 1 감소
			if(cnt1 == cnt2) { // +1물뿌리개 수 = +2물뿌리개수라면 => 가능!!
				System.out.println("YES");
				break;
			}
			else if(cnt1 > cnt2) { // +1물뿌리개 수 > +2물뿌리개수라면 => 불가능!!
				System.out.println("NO");
				break;
			}
		}
	}
	else if(sum%3 == 0 && cnt1 > cnt2){ // 전체 기대높이의 합이 3의 배수이고, +1물뿌리개수 > +2물뿌리개수라면 => 불가능!!
		System.out.println("NO");
	}	
}

- 최적화코드

/**
 * 1짜리 물뿌리개와 2짜리 물뿌리개를 무조건 동시에 사용해야 하므로 
 * 갊자가 바라는 나무의 높이들의 합은 무조건 3의 배수여야 함
 * 
 * 또한 1짜리 물뿌리개는 어디에든 사용할 수 있지만 2짜리 물뿌리개는 남은 높이가 1이하일 경우 사용하지 못하기 때문에
 * 2짜리 물뿌리개를 몇 번 사용할 수 있느냐에 따라 정답이 결정됨
 * 
 * 만약 2짜리 물뿌리개를 사용할 수 없는 횟수가 2짜리 물뿌리개를 사용할 수 있는 횟수 보다 크다면 해당 나무들의 높이는 만들지 못한다.
 * 2이상의 높이는 1짜리 물뿌리개를 사용할 수 있지만 1이하의 높이는 2짜리 물뿌리개를 사용할 수 없기 때문 
 */

public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(br.readLine());
	// 합계
	int sum = 0;
	// 2짜리 물뿌리개를 사용할 수 없는 횟수
	int cnt1 = 0;
	// 2짜리 물뿌리개를 사용할 수 있는 횟수
	int cnt2 = 0;
	StringTokenizer st = new StringTokenizer(br.readLine());
	for(int i=0; i<n; i++) {
		int num = Integer.parseInt(st.nextToken());
		// 
		cnt1 += num % 2;
		cnt2 += num / 2;
		sum += num;
	}
		
	if(sum%3 == 0 && cnt1 <= cnt2) System.out.println("YES");
	else System.out.println("NO");
}