백준 23971번: ZOAC 4

문제 설명

• 전체 WxH 칸에서 최대한 많은 칸을 선택해야 합니다.
• 단 칸과 칸은 세로로 N칸 또는 가로로 N칸 이상 떨어져 있어야 합니다.

접근법

최대한 많은?

최대한 많은칸을 선택하기 위해서는 다음의 조건이 고려되어야 합니다.
1행1열부터 시작해야 합니다.
N칸 혹은 M칸'이상' 떨어지 않고 세로로 N칸'만', 가로로 M칸'만'떨어져야 합니다.

• 직관적으로 다음의 경우를 벗어나면 비효율이 발생하는 걸 이해할 수 있습니다.

규칙성

다음을 생각해 봅시다. 강의실은 가로1 세로5 크기이며, 강의실의 (1,1)에 한 참가자가 앉아있습니다.

1칸을 띄어 앉아야 한다면 (1,3), (1,5) 총 두 명의 참가자가 앉을 수 있습니다. (총 3명)

1	X	2	X	3

2칸을 띄어 앉아야 한다면 (1,4) 혹은 (1,5)에 한 명의 참가자가 앉을 수 있습니다. (총 2명)

1	X	X	2	X

3칸을 띄어 앉아야 한다면 (1,5)에 한 명의 참가자가 앉을 수 있습니다. (총 2명)

1	X	X	X	2

4칸을 띄어 앉아야 하다면 더 이상 참가자가 들어올 수 없습니다. (총 1명)

1	X	X	X	X

• 위 규칙은 (강의실 길이)/(띄어앉은 칸+1)을 올림한 값과 동일합니다.
  • 이를 2차원으로 확장시켜 가로와 세로에 모두 적용시키면 정답을 구할 수 있습니다.

정답

H,W,N,M = list(map(int,input().split(' ')))
#math.ceil()함수는 숫자의 올림을 계산해 줍니다
import math
a = math.ceil(H/(N+1)) # 세로에 몇 명이 앉는지를 계산합니다
b = math.ceil(W/(M+1)) # 가로에 몇 명이 앉는지를 계산합니다
answer = a*b #가로와 세로의 값을 곱합니다
print(answer)

느낀점

• ceil의 개념을 문제에 잘 적용시켰기 때문에 빠르게 풀 수 있었다.
• 왜 math.ceil(H/(N+1))이 성립되지를 만족스럽게 설명하지 못해 아쉽다.

전체 5칸, 띄어앉아야 하는 길이가 4일 때(5/5=1) 딱 1명이 들어오며,
띄어앉아야 하는 길이가 3으로 줄어들 때(5/4=1.25) 1명이 추가되며,
띄어앉아야 하는 길이가 2로 줄어들 때(5/3=1.67) 인원이 변하지 않으며,
띄어앉아야 하는 길이가 1로 줄어들 때(5/2=2/5) 1명이 더 추가되는 규칙이 발견된다