c언어 19539번 사과나무 (백준)

#include <stdio.h>

int main(void)
{
	long long int sum = 0; //전체 나무의 크기 - 반드시 1만큼 자라는 물뿌리개 횟수
	int one = 0; //반드시 1만큼 자라는 물뿌리개 횟수
	int tmp = 0; 
	int n;
	scanf("%d", &n); 
	
	for(int i = 0; i<n; i++) { //반드시 1만큼 자라는 물뿌리개 횟수 + 나머지 나무들의 키 계산
		scanf("%d", &tmp);
		if(tmp&1) { //나무 키가 홀수면 반드시 1만큼 자라는 물뿌리개를 뿌려야함
			one++;
			sum += tmp-1;
		} else sum += tmp;
	} 
	
	if(one*2 > sum) { //1만큼 자라는 물뿌리개를 더 많이 뿌릴수는 없다.
		printf("NO");
		return 0;
	}
	
	sum -= one*2; //1만큼 자라는 물뿌리개와 2만큼 자라는 물뿌리개의 개수는 동등하다.
    
	if(sum%3==0) printf("YES"); 물뿌리개로 한번에 3만큼의 나무의 키를 늘린다.
	else printf("NO");
}

풀이 : 1 증가 물뿌리개 횟수 == 2 증가 물뿌리개 횟수

1) 입력받은 나무의 키 중 홀수가 있다 -> 반드시 한 번 이상은 키가 1 증가하는 물뿌리개를 뿌려야 한다.

 

2) 1 증가 물뿌리개 횟수의 최솟값과, 모든 나무의 키 중 1 증가 물뿌리개 횟수의 최솟값을 뺀 나무의 키들의 합을 구한다.

 

3) 2 증가 물뿌리개 횟수의 최댓값은 2)에서 구한 나무들의 키의 합에 2를 나눈것과 같다.

 

4) 1 증가 물뿌리개 횟수 최솟값 > 2 증가 물뿌리개 횟수 최댓값 일 경우 -> "NO"출력

 

5) 1 증가 물뿌리개 횟수 최솟값 <= 2 증가 물뿌리개 횟수 최댓값 일 경우

 

    일단 1 증가 물뿌리개 횟수  == 2 증가 물뿌리개 횟수 이므로, 알 수 있는 2 증가 물뿌리개 횟수에 2을 곱한 만큼 2)에서 구한 나무의 키들의 합에서 빼준다.

 

6) 5)에서 구한 나무의 키들의 합은 1 증가 물뿌리개 횟수 == 2 증가 물뿌리개 횟수 이므로, 한 번에 나무의 키를 3씩 올림을 의미하며, 이는 나무의 키가 3의 배수가 되어야, YES 임을 알 수 있다.

 

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

19539번: 사과나무