펜윅트리 :: 백준 :: LRH 식물 :: 2934

LRH 식물

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

식물의 이름이 희한하다. LRH.......

예전에 한번 도전해봤는데 무슨말인지 하나도 이해가 가지 않아..

시간이 지나고 다시 도전했다.

물론 지금도 제대로 알고 푼 것 같지는 않다.

알고리즘 분류에는 비트마스크, 펜윅트리라고 분류가 되어 있지만 나는 조금 어거지로 푼 느낌...??

다른 분들 코드 보고 다시 공부해야겠다!

이 문제에 펜윅트리를 어떻게 적용할까 한참 고민하다 굳이 펜윅트리를 적용하지 않아도 풀 수 있겠다는 생각이 들었다.

풀이법을 생각해낸 아이디어는 다음과 같다.

LRH식물은 기둥 두 개와 줄기로 이루어져 있다.

상근이는 매일 LRH 식물을 심는데, 그 높이가 전날보다 항상 1이 높다.(식물의 높이는 1씩 증가한다)

다시 말해 새로 심는 식물의 높이가 항상 가장 높다!

그리고, 줄기와 기둥이 만나는 곳에 꽃이 핀다.

여러 번 만나도 단 한번 꽃이 핀다.