[구름톤 챌린지] 1주차 4일차 완벽한 햄버거 만들기

 

 

문제

---

구름 햄버거는 다양한 재료를 사용하여 만들어서 맛있기로 유명하다. 구름 햄버거는 $N$개의 재료를 순서대로 쌓아서 만들고, 구름 햄버거의 맛은 사용된 모든 재료의 맛의 정도를 더한 값이다.

완벽한 구름 햄버거를 만들기 위해서는 맛의 정도가 가장 높은 재료를 기준으로 위랑 아래로 갈수록 재료의 맛의 정도가 감소하거나 같아야 한다.

플레이어는 $N$개의 재료를 순서대로 쌓아서 구름 햄버거를 하나 만들었다. $i$번째로 쌓은 재료의 맛의 정도가 $k_i$라고 할 때, 플레이어가 만든 구름 햄버거의 맛을 구해보자. 만약 플레이어가 완벽하지 않은 구름 햄버거를 만들었다면 0을 출력한다.

입력

---

첫째 줄에 구름 햄버거에 들어가는 재료의 개수 $N$개가 주어진다.
그다음 줄에 플레이어가 햄버거를 만들 때 쓴 재료의 맛의 정도 $k_1, \cdots, k_N$가 공백을 두고 주어진다.

 

• $1 \leq N \leq 1\ 000$
• $1 \leq k_i \leq 10^6$
• 입력에서 주어지는 모든 수는 정수이다.

출력

---

플레이어가 만든 구름 햄버거의 맛을 출력한다. 만약 플레이어가 완벽하지 않은 구름 햄버거를 만들었다면 0을 출력한다.

 

---

문제 접근 방식

---

완벽한 햄버거는 오름차순 수열과 내림차순 수열이 붙어있는 형태이므로, 완벽한 구름 햄버거를 만드는지 판단할 때 이를 이용했다.

 

먼저 수열의 최댓값을 구한뒤에, 이 최댓값이 가장 먼저 나오는 곳을 기준으로 수열을 분리하여 탐색했다.

 

이후 오름차순과 내림차순을 만족시키지 않는다면 $0$을 출력하도록 하였다.

 

오름차순과 내림차순을 잘 만족시킨다면 합을 출력하도록 했다.

 

---

정답 코드

---

# 완벽한 햄버거 만들기
import sys
input = sys.stdin.readline

N = int(input())
K = list(map(int, input().rstrip().split()))
M = K.index(max(K))
m = 0
flag = True
for i in range(N):
    if i <= M:
        if m <= K[i]:
            m = K[i]
        else:
            flag = False
            print(0)
            break
    else:
        if m >= K[i]:
            m = K[i]
        else:
            flag = False
            print(0)
            break
if flag:
    print(sum(K))

 

---

특별히 배운 점

---

이 문제를 구현하며 max함수, index함수, 오름차순 내림차순 판단, sum함수에 총 $4$번의 전체 배열 탐색이 있었다.

 

이를 오름차순 내림차순 판단에 한꺼번에 처리할 수 있을 것 같다는 생각이 들었다.

 

만약 $N$의 제한이 커졌더라면 조금 귀찮았을 문제인 것 같다.