프로그래밍/컴퓨터 알고리즘

[BOJ] 13136 - Do Not Touch Anything 풀이

포도알77 2019. 4. 4. 21:51

1. 문제

문제

ACM-ICPC 대회의 대회장은 R행 C열의 직사각형 형태로 좌석이 배치되어 있다. 대회가 시작하기 전에는 참가자들이 아무것도 만지면 안 되기 때문에 진행자는 'Do not touch ANYTHING!!!'을 연신 외친다.

하지만, 진행자가 성대결절에 걸리면서 'Do not touch ANYTHING!!!'을 외칠 수 없는 처지가 되었다. 따라서 주최측은 CCTV를 설치하여 참가자들을 감시하려고 한다. 이때, 각 CCTV는 N행 N열의 직사각형 영역의 좌석을 촬영할 수 있다.

모든 좌석을 전부 촬영하도록 CCTV를 배치할 때, 최소 몇 개의 CCTV가 필요할까?

입력

 

첫 번째 줄에 좌석의 세로 크기, 가로 크기 R, C와 한 대의 CCTV가 수용할 수 있는 범위 N이 주어진다. (1 ≤ R, C, N ≤ 1,000,000)

출력

 

모든 좌석을 전부 촬영하도록 CCTV를 배치할 때, 필요한 CCTV의 최소 개수를 출력한다.

예제 입력

7 9 3

예제 출력

9

힌트

 
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

2. 해답

 이 문제는 간단한 사고력을 요하는 문제로, 가로나 세로중 하나를 기준으로 길이 N으로 모두 덮기 위헤서는 ceil(R/N)개가 필요하다. 이후 나머지 변에 대해서도 이는 동일하므로, 결국 R/N과 C/N를 ceil한 두 정수의 곱으로 알 수 있다.

 특히 r,c,n이 각 10^6까지이므로, 최대 10^6*10^6이 된다. 즉 long long을 사용해야 한다.

#include <bits/stdc++.h>
using namespace std;

int r,c,n;
int main(){
    scanf("%d%d%d", &r, &c, &n);
    
    printf("%lld", (long long)(r/n+(r%n>0?1:0))*(c/n+(c%n>0?1:0)));   
}

 

페이스북으로 공유카카오톡으로 공유카카오스토리로 공유트위터로 공유URL 복사