[20/05/24] H 색칠공부(17092)

아이고 이 문제 풀면서 이마를 하도 쳐서 거북목이 나았다

내 구현 능력이 안 좋은 걸 실감하게 했던 문제

스터디 하면서 계속 이걸 왜 못짜지??? 생각 들더라

 

어떻게 풀지는 이해했다

h, w가 10^9라 일일이 탐색할 수 없으니 검은 점을 기준으로 해당 점을 가지는 사각형의 위치에 값을 더해주자!

그런데 이걸 코드로 구현하는 부분에서 머리가 안 돌아가더라

 

 

거의 떠먹이다 싶히 풀었음

하지만 이 당시에는 마음이 너무 급해서 제대로 이해도 못하고 그냥 제출했다.

 

이제 다시 분석하니 알겠음ㅋㅋ

 

이까지는 스터디 때 이해했다.

사각형을 구분 하는 건 저 왼쪽 위 좌표를 기준으로 하겠다

 

 

그런데 점 개수 구하는데서 막혔음ㅋㅋ

 

점을 추가할 때 자기 자신을 기준으로 상하좌우대각선 사각형에 값을 추가해야 하는데 

그럼 x-1, x, x+1 이렇게 저장해야 하는게 아닐까?? 싶었고 그럼 사각형에는 어떻게 추가하지????

 

이 생각에서 막혔었다.

 

지금 다시 보니 이해하겠다.

사각형 잡을 때 기준을 왼쪽 위로 잡았고 그럼 점 개수를 추가할 때 왼쪽 위 사각형을 기준으로 세면 된다.

이 경우에는 x-2, y-2 사각형에 점을 추가해야 하는 거

 

---

이제 이해했으니 이전 코드 안 보고 다시 짜보기..

 

1. 점 입력 받으면서 사각형에 개수 더해주기

 - map을 사용해서 <사각형 위치, 개수> 로 저장한다

2. 점이 없는 사각형 개수 예외처리

3. 출력!

 

아 코드 짜다가 문제가 생겼다

map <ii64, i64> m; 이런식으로 map이 생겨서 auto를 돌리면 i64값이 나올 줄 알았는데 아닌 것 같다. 

 

으음.. 이전 코드를 보니 이렇게 적어놨다.

mi.second라고 하면 y좌표가 나오는 게 아닌가? 나중에 물어봐야겠다.

 

아! map을 순회한 결과가 key, value 두 개 다 나온다.

그래서 key는 first로 접근하고 value는 second로 접근할 수 있다.

 

여기서는 value값이 필요하므로 second로 접근했음

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    i64 h, w, n;
    scanf("%lld %lld %lld", &h, &w, &n);
    
    map <ii64, i64> m;
    for (int i = 0; i < n; i++)
    {
        i64 x, y;
        scanf("%lld %lld", &x, &y);
        
        for (int i = -2; i <= 0; i++)
        {
            for (int j = -2; j <= 0; j++)
            {
                if (1 <= x+i && 1 <= y+j && x+i <= h-2 && y+j <= w-2)
                    m[{x+i, y+j}]++;
            }
        }
    }
    
    vector<int> v(10);
    for (auto mi : m)
        v[mi.second]++;
    
    i64 sum = 0;
    for (int i = 1; i < 10; i++)
        sum += v[i];
    
    cout << (h-2)*(w-2) - sum <<endl;
    for (int i = 1; i < 10; i++)
        cout << v[i] << endl;
    
    return 0;
}

 

다시 짜보니 쉽네