[백준 BOJ] 19539. 사과나무 (UCPC 2020 qualifier H)
07 Jul 2021난이도
Silver I
문제 풀이
문제에서 가장 까다로운 부분은 1과 2만큼 성장시키는 물뿌리개를 동시에 사용해야 한다는 점이다. 물뿌리개가 한 번 시행할 때 마다 어디에 뿌려지고, 어떤 물뿌리개를 쓰는지 생각하는 식으로 문제를 해결하려하면 매우 어려울 것이다. 따라서, 그런 순서를 무시하는 방법으로 문제를 접근하는 편이 옳다고 생각한다.
최종적으로 가능한 경우의 나무 배치라면, (1 성장 물뿌리개 사용 횟수) = (2 성장 물뿌리개 사용 횟수) 임을 자명하게 알 수 있다. 즉, 어떤 순서로 뿌려졌고 어떤 물뿌리개가 쓰였는지 몰라도, 사용횟수가 동일하게 나온다면 순서는 알아서 끼워맞춰진다고 생각할 수 있으니, 사용횟수가 같아질 수 있는지만 체크해주면 되는 것이다.
void solve(int* height, int N) {
int oneCnt = 0, twoCnt = 0;
for(int i = 0; i < N; ++i) {
if(height[i] % 2) oneCnt++;
twoCnt += (int)height[i] / 2;
} //save maximum quotient of two and minimum of one
while(true) {
if(twoCnt == oneCnt) { //'oneCnt == twoCnt' means you can grow trees.
cout << "YES";
break;
}
twoCnt -= 1; //if not, increase oneCnt (2 = 1 * 2)
oneCnt += 2;
if(twoCnt < oneCnt) { //if oneCnt is more than twoCnt, it means you can't grow trees.
cout << "NO";
break;
}
}
}
height는 배열로, 입력받은 나무 배치들의 정보가 담겨있고, N은 심은 나무의 개수이다.
int oneCnt = 0, twoCnt = 0;
for(int i = 0; i < N; ++i) {
if(height[i] % 2) oneCnt++;
twoCnt += (int)height[i] / 2;
} //save maximum quotient of two and minimum of one
이 블럭에서, oneCnt, twoCnt라는 변수에 각각의 사용횟수를 기록한다. (twoCnt가 최대가 되는 방향으로 설정함.)
while(true) {
if(twoCnt == oneCnt) { //'oneCnt == twoCnt' means you can grow trees.
cout << "YES";
break;
}
twoCnt -= 1; //if not, increase oneCnt (2 = 1 * 2)
oneCnt += 2;
if(twoCnt < oneCnt) { //if oneCnt is more than twoCnt, it means you can't grow trees.
cout << "NO";
break;
}
}
while문에서 twoCnt = oneCnt인지 지속적으로 체크한다.
만약 두 물뿌리개의 사용횟수가 같아질 수 있다면, 가능하므로 YES를 출력하고 종료한다.
같지 않다면, (2 성장 물뿌리개)의 사용횟수를 하나 줄이고 (1 성장 물뿌리개)의 사용횟수를 두개 늘려가며 반복문을 돈다.
만약, twoCnt < oneCnt가 되어버리면 불가능한 경우이기에 NO를 출력하고 종료한다.
(twoCnt를 최대로 설정했기에 줄어들며 oneCnt보다 작아진다면, 당연히 같아질 수 없다.)
이렇게 횟수가 같아질 수 있는지만 체크해 출력해주면 되는 문제인 것이다.
발상의 방향이 중요한 비교적 간단한 문제.