백준 23971번 ZOAC 4 - C++

문제

---

2021년 12월, 네 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 오프라인 대회를 대비하여 강의실을 예약하려고 한다.

강의실에서 대회를 치르려면 거리두기 수칙을 지켜야 한다!

한 명씩 앉을 수 있는 테이블이 행마다 W개씩 H행에 걸쳐 있을 때, 모든 참가자는 세로로 N칸 또는 가로로 M칸 이상 비우고 앉아야 한다. 즉, 다른 모든 참가자와 세로줄 번호의 차가 N보다 크거나 가로줄 번호의 차가 M보다 큰 곳에만 앉을 수 있다.

논문과 과제에 시달리는 성우를 위해 강의실이 거리두기 수칙을 지키면서 최대 몇 명을 수용할 수 있는지 구해보자.

 

입력

H, W, N, M이 공백으로 구분되어 주어진다. (0 < H, W, N, M ≤ 50,000)

 

출력

강의실이 수용할 수 있는 최대 인원 수를 출력한다.

 

문제 링크

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

 

 

풀이

---

문제링크에 들어가면 예제 입력과 해답이 그림으로 나와있다.

H가 5, W가 4로 들어오고, 간격이 각각 1인 경우 최대로 배치할 수 있는 인원은 아래와 같다. ▼

 

 

 

"대각선은 안되는건가?"

 

 

문제의 기준에 따르면, X좌표 혹은 Y좌표가 주어진 간격만큼 차이가 나야 떨어진 것으로 간주한다고 한다. ▼

 

 

간격에 대한 기준을 알았으니 이제 구하는 것은 쉽다.

만약 간격이 1이라면, 사람이 앉을 자리 한 칸을 미리 배정해 준 뒤, 오른쪽과 아래쪽에 간격을 더하여 배치를 하면 된다. ▼

 

 

규칙적으로 배치가 되기 때문에 `(너비 / (간격 + 1)) * (높이 / (간격 + 1))`을 해주면 답을 구할 수 있는데, 한 가지 주의할 점이 있다.

사람의 경우엔 아래의 간격이 어떻게 되든, 단 한 칸만 있으면 앉을 수 있다.

그렇기에 간격만큼 자리가 나지 않더라도 단 한 칸만 자리가 나면 사람을 배치할 수 있는 것이기에 `ceil`을 하거나 나눴을 때 나누어 떨어지지 않고 잔여 값이 남으면 `+ 1`을 해준 뒤 곱하면 된다.

▼

 

 

또 하나의 주의점

나누기를 했을 때 나오는 값은 타입은 `double` 이고, `ceil`을 했을 때 나오는 값 또한 `double`이다.

허나 `ceil`을 했을 때 나오는 값의 타입이 아무리 `double`이라고 해도 값은 정수로 반환이 되어 별 생각 없이 둘을 곱한 값을 반환했는데 오류가 났다.

 

`ceil`해서 나온 값을 `long long` 혹은 `int`와 같은 정수형으로 형 변환을 한 뒤 곱해주면 값이 제대로 나오는 것을 알 수 있는데, 이는 아무래도 `double`의 정확도 차이에서 나오는 오류인 것 같다.

 

처음 풀고서 아니 완벽하게 풀었는데 왜지...? 하고 내 접근법 자체가 잘못된건가 싶어서 부끄러움을 무릅쓰고 다른 사람들의 풀이를 봤는데 이 부분이 문제였다...

 

 

C++ 코드

---

#include <iostream>
#include <cmath>

using namespace std;

double H, W ,N, M;

int main() {
    cin >> H >> W >> N >> M;

    cout << (long long)ceil(H / (N + 1)) * (long long)ceil(W / (M + 1));
}

 

`long long`이 아니라 `int` 로 해도 된다.