Logo냥냠감자기술 블로그
Skip to Content
작성일: 2024-01-12

문제

백준 19539 - 사과나무 

  • 난이도: 골드5
  • 알고리즘: 그리디, 수학

코드

#include <iostream> #include <vector> using namespace std; int main() { int n; cin>>n; vector<int> heights(n); for(int i=0; i<n; i++) { cin>>heights[i]; } int sumAll=0; for(int i=0; i<n; i++) { sumAll+=heights[i]; } if(sumAll%3==0) { int usedTimes=sumAll/3; int oddCount=0; for(int i=0; i<n; i++) { if(heights[i]%2==1) { oddCount++; } } if(oddCount>usedTimes) { cout<<"NO"; } else { int remain=usedTimes-oddCount; if(remain%2==0) { cout<<"YES"; } else { cout<<"NO"; } } } else { cout<<"NO"; } }

회고

원래 그리디 알고리즘 문제를 풀고 싶었는데, 막상 문제를 보니 그리디 알고리즘이나 수학 원리를 적용할 부분을 찾지 못했다. 하지만 조건을 잘 나누어 풀면 쉽게 풀 수 있을 것 같아 조건을 잘 나누어 풀어 보았다.