BOJ 13136 - Do Not Touch Anything

문제

BOJ 13136 - Do Not Touch Anything

R x C 크기의 영역을 N x N 크기의 블록으로 나눌 때 필요한 최소 블록 수를 구하라.

입력

R, C, N이 주어진다.

출력

필요한 최소 블록 수를 출력한다.

예제

풀이

행과 열 각각을 N으로 올림 나눗셈한 뒤 곱한다.

1. R을 N으로 나누어 올림한다 (나머지가 있으면 몫 + 1)
2. C를 N으로 나누어 올림한다
3. 두 값을 곱하여 총 블록 수를 출력한다

핵심 아이디어: 2차원 타일링에서 각 축의 올림 나눗셈 결과를 곱하면 총 블록 수가 된다.

코드

#include <iostream>
using namespace std;
 
int main()
{
  long long r, c, n, x, y;
  cin >> r >> c >> n;
  if (r % n)
    x = r / n + 1;
  else
    x = r / n;
  if (c % n)
    y = c / n + 1;
  else
    y = c / n;
  cout << x * y;
  return 0;
}

복잡도

• 시간: O(1)
• 공간: O(1)