https://www.acmicpc.net/problem/2563
문제
> 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다.
> 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다.
> 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.
> 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.
> 첫째 줄에 색종이의 수가 주어진다.
> 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다.
색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고,
두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다.
> 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다
접근
입력으로 받는 두 자연수, 색종이의 왼쪽 변과 도화지의 왼쪽 변사이의 거리, 색종이의 아래변과 도화지의 아래변의 거리를 따져보면 시작점이라고 할 수 있다. 이 점을 시작으로 세로, 가로로 10cm씩 쭉 나가면 색종이가 만들어진다.
그래서 색종이를 놓을 자리를 bool형 크기 10짜리 벡터로 생각하고 색종이가 놓여있으면 그 자리를 true로 준다.
만약 색종이가 겹치게 놓이면 그 자리가 이미 true인지 확인하고 맞으면 스킵한다.
이렇게 하면 색종이가 놓인자리가 겹친대 상관없이 온전히 면적부분만 true가 있다. 이제 이 true의 수를 세면 총 면적이나온다.
문제해결
> 색종이 개수를 입력받아주고 색종이를 담아줄 bool형 이차원벡터를 선언한다.
색종이가 최대 100개까지 가능하므로, 세로로 쭉,가로로 쭉 100개 나열헀을 때 각각 10,1000과 1000,10크기이므로 그냥 1000,1000크기로 벡터를 선언한다.
> 색종이 개수만큼 색종이의 시작점을 입력받아준다.
입력받으면 이 시작점을 반복문의 범위로 잡아 벡터에 bool값을 변화시켜준다.
두 자연수를 각각 r과 c로 받아 행과 열의 시작 범위로 주고, 색종이의 길이가 10이므로 r과 c에 각각 10을 더한 값보다 작을 때까지로 해서 반복문을 돌린다.
> 이제 해당 좌표가 이미 true라면 즉, 전에 이미 색종이를 깔았던자리라면 continue로 해당 면적을 한번만 카운팅할 수 있도록한다.
> true가아니면 true로 값을 변화시켜 색종이를 깔아주고 깔면서 동시에 cnt값을 누적시킨다. 즉 면적을 세는 과정이다.
> 누적된 면적을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<vector<bool>> pos(1000, vector<bool>(1000, false));
int cnt = 0;
while (N--)
{
int r, c;
cin >> r >> c;
for (int i = r; i < r + 10; i++)
{
for (int j = c; j < c + 10; j++)
{
if (pos[i][j]) continue;
pos[i][j] = true;
cnt++;
}
}
}
cout << cnt << '\n';
}
후기
bool로 해서 겹친곳은 마킹을 해놓고 나중에 true인 지점을 다 세서 면적을 구하는 아이디어는 금방생각했는데
색종이를 찍는 좌표의 처리가 문제였다.
처음엔 이를 점으로 생각해 3,7부터 10의 크기니까 13, 17까지 해서 점을 세면 색종이 하나당 점의 수가 121개가 나오고 겹치는데 따지면 또 문제가 생겨 이를 수식화해서 어떻게 처리해야 하나 했다.
계속 생각하다 이를 점이 아닌 칸, 면적으로 생각해서 1,1 네모칸 으로 생각해서 하면 인덱스상으로 3부터 12까지가 되지만 길이는 10cm로 맞아 떨어진다. 그래서 칸을 생각해서 했더니 해결됐다.
계속 노려보면 답이 나오긴한다.
