2022. 11. 13. 15:37ㆍSilver/Silver III
상당히 최근에 올라온 문제다. 아마 1주일도 안 되었을 것이다.
그래도 이 문제를 푸는 데 필요한 직관이 생각보다는 중요할 것 같아서 글을 쓰게 되었다.
나만 이렇게 생각했나 했는데 다들 이런 방법으로 풀더라.
그럼 본격적으로 풀이에 돌입해 보자.
문제
항구의 컨테이너 하치장 바닥에는 컨테이너를 쌓을 수 있는 칸이 일렬로 총 n개가 그려져 있고, 현재 하치장에는 총 m개의 컨테이너가 쌓여 있다. 개별 컨테이너의 높이는 모두 1로 동일하며, 각 칸에 쌓을 수 있는 컨테이너의 개수에는 제한이 없다. 즉,
현재와 같이 높이에 아무 제한이 없이 컨테이너가 쌓여 있을 경우 각 칸별로 쌓여있는 컨테이너의 개수의 차이가 심하여 안전상 문제점을 유발할 수 있기 때문에, 일부 컨테이너를 크레인을 이용하여 다른 칸으로 옮겨서 각 칸의 높이 차이가 1이하가 되도록 재배치하고자 한다. 즉, 임의의 i, j에 대해
예를 들어 <그림 1>과 같이 35개의 컨테이너가 8개의 칸에 쌓여 있을 경우 m = 35, n = 8에해당한다. 이를 높이 차이가 1 이하가 되도록 재배치하면 <그림 2>와 같은 결과를 얻을 수 있고, 이 경우 5개의 컨테이너를 옮겨야 한다.


입력으로 각 칸에 초기에 쌓여 있는 컨테이너의 높이
입력
입력은 표준입력을 사용한다. 첫 번째 줄에 컨테이너를 쌓을 수 있는 칸의 개수를 나타내는 양의 정수 n (1 ≤ n ≤
예제 입력)
# 예제 입력 1
4
1 2 3 3
# 예제 입력 2
8
5 6 7 2 3 4 2 6
출력
출력은 표준출력을 사용한다. 문제의 조건을 만족하기 위해 옮겨야 하는 컨테이너의 최소 개수를 한 줄에 출력한다.
예제 출력)
# 예제 출력 1
1
# 예제 출력 2
5
내 코드
n, cnt1, cnt2 = int(input()), 0, 0
l = list(map(int, input().split()))
avg = sum(l) // n
for i in l:
if i > avg+1: cnt1 += (i-avg-1)
elif i < avg: cnt2 += (avg-i)
print(max(cnt1, cnt2))
문제 조건에 너무 겁을 먹지 마라.
임의의 i, j에 대해
그렇다면 재배치 후 i번째 칸에 쌓여 있는 컨테이너 개수를
그러면 간단한 부등식 하나가 만들어지는데, 이는 다음과 같다.
줄이면?
그럼 이제 <그림 3>을 통해서 한 번 보자. 예제 그림을 살짝 매만진 것이다.
예제에는 35개의 컨테이너와 8개의 줄이 있고, 따라서 여기서는 x=4가 된다. 이를 파란 줄로, x+1을 빨간 줄로 표기했다.

노란색 컨테이너는 빨간 선을 초과했으니까 어딘가로 옮겨서 낮춰야 하는 양이고, 초록색 빈 공간은 파란 선에도 못 미치니 어디선가 컨테이너를 찾아와서 채워야 하는 양이다.
그렇다면 노란색의 총 수와 초록색의 총 수 중 더 큰 쪽만 찾아서 출력하면 될 일이다. 만약 노란색 컨테이너가 남는다면 임의의 x 높이를 가진 컨테이너 줄에 올려버리면 되고, 초록색 빈 공간이 남는다면 임의의 x+1 높이를 가진 컨터이너 줄에서 하나를 가져와서 채우면 될 테니 말이다.
cnt1, cnt2를 각각 노란색 컨테이너, 초록색 빈 공간의 총량을 세는 변수로 지정한 다음,
마지막에 그 둘을 비교한 다음 더 큰 값을 출력하면 끝.
이로서 25945번의 풀이를 마친다.

'Silver > Silver III' 카테고리의 다른 글
BOJ 9095 - 1, 2, 3 더하기 (Python3) (0) | 2022.11.13 |
---|---|
BOJ 9659 - 돌 게임 5 (Python3) (0) | 2022.11.12 |