[2023-01-21]

Start

 

Flags 문제

peak P는 배열 A에서 A[P - 1] < A[P] 와 A[P] > A[P + 1] 을 만족해야한다.

이 peak P 위치에는 Flag를 꽂을 수 있고 꽂으려고 하는 Flag의 수만큼 간격을 띄워야한다.

어제 마지막보다 정확도는 조금 올랐는데 내가 짠 로직 자체가 문제가 있는 것 같아서 새롭게 다시 짜려고 한다.

 

1. peak 수와 위치를 파악했다.

2. 파악한 peak 수만큼을 최대 Flag 개수라고 두고 '최대 Flag 개수'에서 1까지 대입해보며 꽂을 수 있는 가장 큰 Flag를 구한다.

 

최대 flag 일 경우 flag 개수는 많지만 그만큼 distance를 띄워야하기 때문에 많은 flag를 꽂을 수가 없다.

그래서 최대 flag 개수부터 1까지 대입해보면서 꽂을 수 있는 최대 flag 개수를 갱신하고

최대 flag 개수보다 작은 수가 나올 경우 대입을 멈추고 결과를 도출하는 식으로 했다.

 

 

정답을 찾아보았는데, 좀 재밌는 이야기를 한 것 같다.

사실 peak 수 만큼 다 꽂을 수 있는 것이 아니었는데,

첫번째 peak부터 마지막 peak까지의 차이를 실질적 배열의 크기로 하고 제곱근을 구하면 좋을 것 같다.

 

 

위의 방법을 적용해서 min_flag 부터 peak 개수만큼 돌면서 flag를 꽂아보았는데, 아직 뭐가 안되는지 잘 안된다..ㅜㅜ허어헝헝