티스토리 뷰
문제 링크 : https://www.acmicpc.net/problem/19539
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int sum = 0;
int cnt2 = 0;
for (int i = 0; i < n; i++)
{
int h;
cin >> h;
sum += h;
cnt2 += h / 2; //다른 물뿌리개 가능 횟수
}
if (sum % 3 != 0 || cnt2 < sum / 3) cout << "NO";
else cout << "YES";
return 0;
}
기본적으로 나무 하나를 1만큼 성장시키거나, 2만큼 성장시키기에 한 번에 3만큼 성장시킨다는 것을 알 수 있다.
따라서 나무 높이의 합산이 3의 배수여야만 물뿌리개를 모두 알맞게 사용할 수가 있다.
하지만 3의 배수를 체크하는 것만으로는 부족하다.
아래의 예시의 경우 3의 배수이지만, 2만큼 성장시키는 물뿌리개의 사용이 불가능한 케이스이다.
1 1 1 3 3 3
따라서 추가적으로 2만큼 성장시키는 물뿌리개의 가능 회수 또한 체크하여야 한다.
이를 위해 입력받은 높이에 대해 2로 나누어 해당 물뿌리개 사용 가능 회수를 카운팅한다.
이렇게 구한 회수는 총 물 뿌리개 사용 회수라고 할 수 있는 sum/3의 값보다 작으면 균형이 맞지 않아 불가능한 케이스므로 NO를 출력한다.
'백준 > 골드' 카테고리의 다른 글
[백준 28069번] 김밥천국의 계단 (C++) (0) | 2025.05.08 |
---|---|
[백준 10422번] 괄호 (C++) (0) | 2025.05.07 |
[백준 1253번] 좋다 (C++) (0) | 2025.05.04 |
[백준 2877번] 4와 7 (C++) (0) | 2025.04.30 |
[백준 1790번] 수 이어 쓰기 2 (C++) (0) | 2025.04.29 |