[PS] BOJ 21965 / 드높은 남산 위에 우뚝 선

Minjun Kim

14 May 2025 • 2 min read

문제 링크: https://www.acmicpc.net/problem/21965

Thumbnail: Photo by Ales Krivec (Unsplash)

마냥 간단하게 생각했었는데, 생각보다 실수하기 쉬운 문제였습니다.

풀이

문제에서 어떤 수열을 산이라고 부르기 위한 조건은 간단히 요약해보면,

"수열의 원소들은 임의의 지점 전까지 계속 증가하다가 이후로는 계속 감소해야 한다." 입니다.

구현에 필요한 조건들을 정리해 보면 다음과 같습니다:

주어진 수열은 임의의 지점까지 증가하다가 그 후로는 감소한다.
- 연속해서 같은 수가 나올 수 없다! (증가 or 감소 모두 아니기 때문)
한 번 감소하기 시작한 뒤로는 계속 감소해야 한다.
- 감소하기 시작한 지점을 파악해야 한다.

전체 코드

input = open(0).readline
N = int(input())
A = list(map(int, input().split()))

result = True       # 결과값을 나타내는 변수
idx = 0             # idx는 감소하기 직전의 인덱스, 즉 순열 내에서 가장 큰 값의 인덱스가 된다.
idx_lock = False    # 한 번 감소하기 시작한 뒤로는 다시 증가해선 안된다.
for i in range(1, N):
    if A[i] == A[i - 1] or (idx_lock and i > idx and A[i] > A[i - 1]):  # 중복된 수가 존재하거나, 감소한 뒤로 다시 증가하는 경우
        result = False
        break
    
    if not idx_lock:            # 최초 감소하는 지점을 찾기 위한 조건문.
        if A[i] > A[i-1]:
            idx = i
        elif A[i] < A[i-1]:
            idx_lock = True
        
print("YES" if result else "NO")

solution.py