[C++] 백준 23971: ZOAC 4

문제

[C++] 백준 23971: ZOAC 4 BRONZE 3
https://www.acmicpc.net/problem/23971

 

---

 

접근 방법

이 문제는 강의실의 크기와 거리 제한이 주어졌을 때 사람을 최대로 배치할 수 있는 개수를 구하는 문제이다.

 

처음에는 2차원 벡터를 선언한 뒤,
사람을 앉힐 수 있는 위치에만 표시하면서 하나씩 카운팅하는 방식으로 접근했다.
하지만 이 방법은 불필요한 반복이 많아 시간 초과로 계속 실패했다.

 

곰곰이 생각해보니 굳이 모든 좌석을 직접 확인할 필요가 없었고,
행과 열 각각에서 앉을 수 있는 개수를 공식으로 계산하면 되는 문제였다.

 

세로 방향에서는 (n+1)칸마다 한 명,
가로 방향에서는 (m+1)칸마다 한 명씩 앉을 수 있으므로
각각 ceil(h / (n+1)), ceil(w / (m+1))을 계산해 곱해주면 된다.

 

처음부터 공식을 떠올렸다면 훨씬 빨리 풀 수 있었던 문제라
약간 멍청한 짓을 했다는 생각이 들었다..ㅠ

 

구현 시 주의할 점

나눗셈 결과가 소수일 경우를 고려해 ceil을 사용해 올림 처리해야 한다.

 

h를 (n+1)로 나눈 값은 “사람 간격 묶음이 몇 개 들어가냐”인데,
나머지가 있으면 끝에 한 명을 더 앉힐 수 있으므로 올림(ceil) 이 필요하다.

 

---

 

코드

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    double h = 0, w = 0, n = 0, m = 0;
    cin >> h >> w >> n >> m;

    cout << (int)ceil(h / (n + 1)) * (int)ceil(w / (m + 1));

    return 0;
}