[Baekjoon] 17392. 우울한 방학 - python

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

17392번: 우울한 방학

문제 정보

문제 유형	난이도	걸린 시간	해결 유무
그리디	실버1	1h	o

설계 방법

• sum : 0까지는 우울하지 않으니까 arr의 모든 값에 1을 더해줌
• left : m - sum # 우울한 날
• n+1 : 우울한 날이 들어갈 수 있는 칸
• 예시(3 10 2 2 1)의 경우에는 들어갈 수 있는 칸이 4개인데 우울한 날이 2이므로 1의 제곱 * 2 이 우울의 총합이 된다
  • 만약 들어갈 수 있는 칸이 4개인데 우울한 날이 5이였으면
  • -1, -1, -1, -1 먼저 들어가고 나머지 한개 -2의 제곱 더해주는 것

코드

n,m = map(int, input().split())
answer = 0
sum = 0
left = 0

arr = list(map(int, input().split()))
for i in arr:
    sum += i + 1 # 0까지는 우울하지 않으니까 + 1

if sum < m:
    left = m - sum # 나머지 
    div1 = left // (n + 1) # 들어갈 수 있는 칸의 수 
    div2 = left % (n + 1) 
    for i in range(1, div1 + 1):
        answer += i ** 2 * (n + 1)
    answer += (div1 + 1) ** 2 * div2

print(answer)

시간 복잡도

O(n)

어려웠던 점

들어가는 공간에 대해 구현하는 것이 힘들었음