[구름] 구름공원 - 파이썬

문제

🔗 : https://level.goorm.io/exam/51354/구름공원/quiz/1

깨끗하게 관리가 잘 되어있기로 소문난 구름공원에는 N개의 벤치가 있다. 현재 i번째 벤치에는 A_i명의 사람이 앉아있는데, 구름공원을 찾아온 M명의 사람들이 벤치에 추가로 앉으려고 한다.

 

M명의 사람들이 N개의 벤치에 각자 잘 나눠앉았다고 할 때, 사람이 가장 많이 앉아있는 벤치를 찾는다. 그 벤치에 앉아있는 사람의 수를 K라고 하자. 가능한 K의 값 중 최솟값과 최댓값을 각각 구하여라.

 

입력

첫째 줄에 벤치의 수와 구름공원에 찾아온 사람의 수를 나타내는 정수 N, M이 공백을 두고 주어진다.

둘째 줄에 각 벤치에 앉아있는 사람의 수 A₁, A₂, ... , A_N이 공백으로 구분되어 정수로 주어진다.

 

• 1 ≤ N ≤ 2 X 10⁵
• 1 ≤ M ≤ 10⁹
• 0 ≤ A_i ≤ 10⁶
• 입력으로 주어지는 모든수는 정수이다.

 

출력

구름공원을 찾아온 M명의 사람이 벤치에 추가로 앉았을 때, 사람이 가장 많이 앉아있는 벤치를 찾는다. 그 벤치에 앉아있는 사람의 수 K에 대해, 가능한 K의 값 중 최솟값과 최댓값을 출력한다.

예시 1

입력

4 6
1 1 1 1

출력

3 7

 

---

파이썬이랑 친해지기 연습단계로 풀었다.

수학..?인지 애매한 간단한 구현문제

 

사람이 가장 많이 앉은 벤치의 인원 수를 K라고 할 때, K값의 최댓값은 단순히 '몰아 앉은 경우' 이다.

M명의 사람들이 N개의 벤치에 사이좋게 나눠 앉지 않고,

원래 가장 많이 앉아있는 벤치에 M명의 인원이 몰아 앉을 때 가장 최댓값이 된다.

K_max = max(bench) + M

 

K값의 최솟값은 원래 벤치에 앉아있던 사람들과 새로 들어올 M명의 사람들이 N개의 벤치에 최대한 골고루 앉았을 때 가장 많이 앉아있는 벤치가 될 수 있다.

 

예를 들면,

 

입력 예시 1과 같이 4개의 벤치에 각각 1명씩 앉아있고 6명의 사람이 새로 앉으려고 할 때

기존 인원 4명 + 새로 들어온 인원 6명 총 10명의 인원이 4개의 벤치에 가장 골고루 앉는 방법은

3 3 2 2 로 앉는 방법이다. 이 때의 K값은 3이 된다.

 

 

마찬가지로 3개의 벤치에 각각 1명, 6명, 5명이 앉아있고 6명의 사람이 새로 앉으려고 할 때

기존 인원 12명 + 새로 들어온 인원 6명 총 18명의 인원이 3개의 벤치에 골고루 앉는 방법은

6 6 6 으로 앉는 방법일 것이다. 마찬가지로 이 때의 K값은 6이 된다.

 

 

근데 이렇게 풀면 생각해봐야 할 점이 한 벤치에 몰려앉아있을 때 라서,

3개의 벤치에 10명, 0명, 0명이 앉아있고 10명의 인원이 새로 앉으려고 할 때,

총 20명의 인원이 3개의 벤치에 골고루 앉으려고 하면 7 7 6 이겠지만,

원래 첫번째 벤치에 10명이 앉아있으니 새로 들어온 인원들이 나머지 두개의 벤치에 어떻게 나눠앉아도 K값은 10이다.

 

따라서 K의 최솟값은 다음과 같이 구해준다.

K_min = (M + sumation) // N if (M + sumation) % N == 0 else ((M + sumation) // N) + 1

K_min = max(maximum, K_min)

 

파이썬 편해서 좋구만..

 

코드

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
N, M = map(int, input().split())

bench = list(map(int, input().split()))

sumation = sum(bench)
maximum = max(bench)

K_max = maximum + M
K_min = (M + sumation) // N if (M + sumation) % N == 0 else ((M + sumation) // N) + 1

K_min = max(maximum, K_min)

print(K_min, K_max)