어떤 규칙을 관찰하셨고, 어떤 풀이를 하셨는지 알려주시면 좀 더 좋은 답변을 들을 수 있을 거 같아요

아. 질문이 좀 부족했습니다 ㅎ

우선 숫자 3개를 예시로 놓았고, 순서를 바꿔가면서 관찰한 결과 maximum에 해당하는 숫자를 바꿔야 한다는 걸 처음으로 확인했습니다.

거기에, 첫 예시의 숫자3개와 더불어 연결된 다른 숫자3개를 더 적어서 관찰한 결과 해당문제의 에디토리얼에서 제공하는 것과 같은 결론에 도달했습니다.

근데, 제가 낸 그 결론이, 입력되는 모든n에 대해 성립하는가?에 대한 증명을 못하겠습니다...

공부를 이제 막 시작한 사람이라, 기초문제에 집중하며 코드구현 연습을 하고 있는데... 종만북에서 가능하면 정당성 증명도 꾸준히 하는 게 좋다라는 내용을 보고

시도는 해보고 있습니다만... 이렇게 쉬운 문제에서도 금방 떠오르지가 않네요;;;

늦은 새벽 답변 감사드립니다 :)

앞에서부터 차례대로 확인하면서 일단 앞쪽의 local maximum들을 최소 횟수로 없애왔다고 가정해 봅시다.

그러다가 중간에 a_i를 만났는데, 이 친구가 local maximum인걸 알게 된거죠.
그럼 계속 최소횟수를 유지하면서 local maximum을 없애려면 local maximum의 정의상 a_i 혹은 그 앞 뒤의 값을 하나는 바꿔야 합니다.

이건 셋 중 하나만 바꾸는게 유리하다는 건 당연합니다. 세가지 케이스를 나눠서 생각해봅시다.

1) a_i-1을 바꾼 경우
그보다 앞에는 이미 local maximum이 없다고 가정했으므로 최대 1개의 local maximum을 없앨 수 있습니다.

2) a_i를 바꾼 경우
local maximum은 정의 상 연달아 있을 수 없으므로, 이때도 최대 1개의 local maximum을 없앨 수 있습니다.

3) a_i-1을 바꾼경우
이 경우에는 editorial에도 나와있듯이 max(a_i,a_i+2)의 값으로 바꾸면 최대 2개까지 local maximum을 없앨 수 있습니다.

3)을 선택하는 것이 차후 a_i+3까지의 미래를 내다봤을 때 이는 다른 경우에 비해 절대 손해 보지 않는 선택이며, 그 이후의 상황은 서로 동등합니다.
따라서 매번 3)을 선택하는 것이 이득이겠군요.

사실 그리디는 이 '손해보지 않는 선택' 이라는게 꽤 핵심이 되는 편이니 이걸 찾는 식으로 증명하면 좋습니다.
저도 아직 많이 부족한 사람이지만, 이 글이 도움이 되셨으면 좋겠네요.

3)에 오타가 있는데 a_i+1을 잘못 쓴겁니다.. 왜 글 수정기능이 없을까요

답글을 이제야 봤습니다.

정성스런 답변 감사드려요 ㅠㅠ

계속 해나가보겠습니다 ㅎ