백준 | ZOAC 4

백준 ZOAC 4 문제 풀이이다.

최대한 많은 사람이 앉으려면 공간을 아껴야 하므로, (1, 1)에 참가자를 앉힌다고 가정했다.

이제 이 참가자를 기준으로 안전 거리(세로: n, 가로: m)를 고려하여 한 명씩 붙여 앉히면 된다.

사람이 차지하는 공간(세로: 1, 가로: 1)에 안전 거리까지 고려하면, 한 사람이 앉을 때 차지하게 되는 공간은 세로 n + 1, 가로 m + 1이 된다.

그래서 h X w 크기의 직사각형 강의실에 (n + 1) X (m + 1) 사이즈의 블럭을 채우는 문제로 바꿔서 생각할 수 있다.

그런데 아래 그림의 세로처럼, 세로나 가로의 끝 부분에 (n + 1) X (m + 1) 사이즈의 블럭이 온전히 들어갈 수 없어도, 공간이 있기만 하면 1명은 더 앉힐 수 있다.

즉, 1 이상의 공간이 남는다면 1명을 더 앉힐 수 있는 것이다.

그래서 (강의실 세로) % (한 블럭의 세로)가 0이 아니면 세로 인원에 1명을 추가해줬다. (가로도 마찬가지이다.)

최종 정답은 이렇게 구한 세로 인원과 가로 인원의 곱이다.

코드(정답)는 다음과 같다.

import sys


h, w, n, m = map(int, sys.stdin.readline().split())

# 세로에 앉을 수 있는 인원
if h % (n + 1) :
    y = h // (n + 1) + 1
else:
    y = h // (n + 1)

# 가로에 앉을 수 있는 인원
if w % (m + 1):
    x = w // (m + 1) + 1
else:
    x = w // (m + 1)

# 강의실에 앉을 수 있는 최대 인원
print(y * x)

위의 풀이도 결국 '올림(ceil)' 개념을 이용한 것인데, 파이썬의 math.ceil을 사용해서 푼 분들이 많았다.

import sys
import math


h, w, n, m = map(int, sys.stdin.readline().split())

# 세로에 앉을 수 있는 인원
y = math.ceil(h / (n + 1))

# 가로에 앉을 수 있는 인원
x = math.ceil(w / (m + 1))

# 강의실에 앉을 수 있는 최대 인원
print(y * x)