https://www.acmicpc.net/problem/24729
문제요약
- 숫자가 주어짐(5만개, 1 ~ 10만)
- 계단수를 만들수 있는가? : 앞/뒤 숫자가 +1, -1 이면서 시작/끝도 +1, -1
접근법
- 시작/끝이 +1, -1이므로 연결이 됨 => 어떤 숫자에서 시작해도 상관없어야함
- 가장 작은 숫자부터 시작했다면? 끝은 가장 작은 숫자 +1 이어야함
- 일단 입력이 홀수개이면 못만듬 => 올라간만큼 내려오니까 최소값+1 이 안됨
- 최종 모습은 숫자가 오르락 내리락 하다가 정상(최대값)을 찍고 다시 오르락 내리락 하다가 끝날 것임
- 오르락 내리락의 특징은 한번 갔다가 다시 제자리로 온다는 것임
- 1 2 3 4 3 2 3 4 3 2 (내려갔다 올라오는 부분을 굵게 표시해봄)
- 모양을 짧게 내려갔다 오는 것으로 바꿀 수 있음
- 4 -> 3 -> 2 -> 3 -> 4까지 내려갔다 오는 부분을 변형해보면
- 1 2 3 2 3 4 3 4 3 2 (굵게 표시한부분이 기본 수열에서 내려갔다 올라왔다를 처리한 부분임)
- 그래서 일단 오르락 내리락이 없다고 치고 최소 => 최대 => 최소 + 1로 가능한지 판단함
- 그리고 나서 각각의 숫자에 대해서 내려갔다가 올라올 수 있는지 판단함
- 내려가는 숫자가 없으면 => 다음
- 내려가는 숫자가 있는데
- 올라올 수 있으면 => 처리하고 다음
- 올라올 수 없으면 => 실패
- 이렇게 다 했는데 남아있는 숫자가 없으면 성공, 있으면 실패
newbieski