[Baekjoon 32173] 새치기 | Python

https://www.acmicpc.net/problem/32173

---

문제

 

학생들이 식당에 줄을 설 때 가장 앞, 가장 뒤 중 하나를 선택하여 설 수 있다. 이때 만족도가 변하는데, 경우의 수 중 가장 높은 만족도를 구하는 문제이다.

 

---

풀이

 

학생에게는 맨 앞에 서거나, 맨 뒤에 서는 두 가지 선택지밖에 없다. 즉 두 경우의 수 중 무엇이 만족도 총합을 가장 높게 하는지 확인하면 된다.

조건에 따르면 가장 앞에 서게되면 가장 앞에 서는 학생의 만족도 만큼 총 만족도가 올라가지만, 현재 서있는 학생들의 만족도의 합만큼 총 만족도가 감소하게 된다. 그러나 가장 뒤에 서게되면 해당 학생의 만족도는 0 이므로 총 만족도는 변화하지 않는다. 따라서 어떤 학생이 맨 앞에 서느냐가 만족도에 영향을 준다는 것을 알 수 있다.

그런데 생각해보면 어떤 학생이 가장 앞에 서게되면 이미 서있던 모든 학생들의 만족도만큼 총 만족도가 감소하므로 가장 앞에 서게되는 학생의 만족도가 이미 서있던 모든 학생들의 만족도보다 클 때만 가장 앞에 서는 것이 총 만족도를 높일 수 있다. 또한 새치기가 여러번 일어난다고 해서 만족도가 감소한 학생들의 만족도가 변하는 것은 아니므로 새치기의 횟수 자체는 몇 번이든 상관이 없다.

따라서 새치기를 하게되는 경우를 확인하고, 그 중 가장 큰 총 만족도를 구해야한다.

누적된 학생들의 총 만족도는 슬라이싱과 sum 을 사용해도 구할 수 있지만, 그것보다는 누적 만족도 변수를 하나 만들어서 계산하는 것이 효율적이다.

 

---

코드

 

student_n = int(input())
happy = list(map(int, input().split()))
total_happy = 0
max_happy = 0
for i in range(student_n):
    if happy[i] > total_happy:
        max_happy = max(max_happy, happy[i] - total_happy)
    total_happy += happy[i]
print(max_happy)