BOJ

BOJ::1184 귀농

BOJ Gold 1

BOJ::1184 귀농

Link : BOJ::1184
Link : COCI
Level : Gold 1

시사점

정말 좋은 문제라고 생각합니다.
특히 저에게 좋은 문제였습니다.
2개의 작업을 직렬로 풀이하여 4중 for문이 나오던 것을, 2개의 작업을 병렬로 풀이하여 2중 for문으로 수정하여 맞은 문제입니다.
- 즉, 조금 더 체적화가 가능했습니다.
- naive에서 접근해서 최적화를 해갈때, 더 최적화할 수 있는지 심도있게 고민하여야 할 것 같습니다.
또한 사각형의 합을 구하는 psum도 자주 사용하는 방법이므로 익혀두면 좋을 것 같습니다.

키

#수익, #꼭짓점 하나

이해(x)

N * N 의 맵이 주어집니다.
이 맵에서 문제의 조건을 만족시키는 방법의 수를 출력합니다.
- 조건은 다음과 같습니다.
- 꼭짓점 하나만 공유하는 정사각형 두 개를 선택합니다.
  - 이때, 정사각형은 변을 공유할 수 없습니다.
  - 두 정사각형에 포함된 값의 합이 동일하다면 방법의수를 하나 늘립니다.

설계, 손 코딩(x)

손으로 중심이 되는 코드를 구현합니다.
이해를 돕기 위해 그림으로 표현하였습니다.
naive of naive부터 최적화해나가는 과정입니다.

naive of naive

처음 들었던 생각을 그림으로 표현하였습니다.
빨간 점을 통해 시작점을 Fix하고,
- 사각형 A를 선택합니다.
- 이후, A와 꼭짓점을 공유하는 사각형 4개를 떠올릴 수 있습니다.

최적화 1

생각해보면, A와 꼭짓점을 공유하는 사각형은 굳이 4개일 필요가없습니다.
해당 내용들은 모두 아래 그림으로 커버가 가능합니다.
즉, A하나당 B는 2가지 종류만 있으면 전체 경우의 수를 커버할 수 있습니다.
따라서 최초 접근을 아래와 같이 풀이하였습니다.
하지만, 자세히 들여다보면
빨간점을 Fix하는데 2중 for문
- A의 가로 사이즈와 세로 사이즈를 Fix하는데 2중 for문
  - B1의 가로 사이즈와 세로 사이즈를 Fix 하는데 2중 for문
  - 혹은 B2의 가로 사이즈와 세로 사이즈를 Fix하는데 2중 for문
즉 6중 for문이 되어 N = 50인 상황에서 시간초과를 유발합니다.

최적화 2

6중 for문을 벗어날 방법이 떠오르지 않았습니다.
하지만 아래와 같이 한다면 시사점 챕터에서 설명하였듯이, 직렬로 연결된 4중 for문을 2중 for문 2개로 풀이할 수 있습니다.
자세히 들여다보자면,
- 빨간점을 Fix합니다 ( 2중 for문 )
  - A의 가로 사이즈와 세로 사이즈를 Fix합니다. ( 2중 for문 )
    - 이때, 해당 A 사각형의 합을 map에 insert합니다.
  - 이후, B의 가로 사이즈와 세로 사이즈를 Fix합니다. ( 2중 for문 )
    - 이때, 해당 B 사각형의 합이 이미 map에 들어있는 경우 정답에 더합니다.
즉, 꼭짓점을 공유하기때문에 과정 1과 과정 2를 병렬로 처리하는 것이 합당합니다.

시간 복잡도

O(N^4) * O(logN(map에서 꺼내거나 insert하는 시간입니다))

공간 복잡도

손 코딩 후 문제 리뷰(x)

빼먹고 손 코딩 한 것이 있는지 확인합니다.

구현(x)

함수 List

// psum을 미리 구합니다.
void precalc();

// 꼭짓점이 (x,y)이고, 반대편이 (nx, ny)인 사각형의 합을 반환합니다.
int rectSum(int nx, int ny, int x, int y);

// 그림(a)에 표현된 사각형 2개의 포지션입니다.
void LeftUp_RightDown(int x, int y);

// 그림(b)에 표현된 사각형 2개의 포지션입니다.
void LeftDown_RightUp(int x, int y);

업데이트 되는 변수

대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.

// 업데이트 되는 변수 -------------------------------------------------------
int psum[MAXN][MAXN]; // psum[i][j] : (1,1)부터 (i,j)까지의 사각형의 합
map<int, int> mp;  // 사각형의 합을 처리할때 사용하는 map
// 업데이트 되는 변수 -------------------------------------------------------

실제 구현

#include<iostream>
#include<map>
#define rep(i, a, b) for(int i=a;i<b;i++)
const int MAXN = 50 + 2;
using namespace std;

int n, ans;
int a[MAXN][MAXN];
int psum[MAXN][MAXN]; //  // psum[i][j] : (1,1)부터 (i,j)까지의 사각형의 합
map<int, int> mp; // 사각형의 합을 처리할때 사용하는 map

// psum을 미리 구합니다.
void precalc(){
    psum[1][1] = a[1][1];
    rep(i, 1, n + 1) rep(j, 1, n + 1)
    psum[i][j] = psum[i - 1][j] + psum[i][j - 1] + - psum[i-1][j-1] + a[i][j];
}

// 꼭짓점이 (x,y)이고, 반대편이 (nx, ny)인 사각형의 합을 반환합니다.
int rectSum(int x, int y, int nx, int ny){
    return psum[nx][ny] - (psum[nx][y-1] + psum[x-1][ny]) + psum[x-1][y-1];
}

// 그림(a)에 표현된 사각형 2개의 포지션입니다.
void LeftUp_RightDown(int x, int y){
    mp.clear();
    for (int i = x; i >= 1; i--) {
        for (int j = y; j >= 1; j--) {
            int rect = rectSum(i, j, x, y);
            if (mp.count(rect)) mp[rect]++;
            else mp[rect] = 1;
        }
    }
    for (int i = x + 1; i <= n; i++) {
        for (int j = y + 1; j <= n; j++) {
            int rect = rectSum(x + 1, y + 1, i, j);
            if (mp.count(rect)) ans += mp[rect];
        }
    }
}

// 그림(b)에 표현된 사각형 2개의 포지션입니다.
void LeftDown_RightUp(int x, int y){
    mp.clear();
    for (int i = x; i >= 1; i--) {
        for (int j = y; j <= n; j++) {
            int rect = rectSum(i, y, x, j);
            if (mp.count(rect)) mp[rect]++;
            else mp[rect] = 1;
        }
    }
    for (int i = x + 1; i <= n; i++) {
        for (int j = y - 1; j >= 1; j--) {
            int rect = rectSum(x + 1, j, i, y - 1);
            if (mp.count(rect)) ans += mp[rect];
        }
    }
}
// 디버깅 다 해봤는데 틀리는 거 보면,, 시작점을 어떤 사각형에 포함하냐인듯
// 블로그에 올린 사람이랑 같은 범위의 사각형으로 시도해보기


int main(){
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    rep(i, 1, n + 1) rep(j, 1, n + 1) cin >> a[i][j];
    precalc();

    rep(i, 1, n + 1){
        rep(j, 1, n + 1){
            LeftUp_RightDown(i, j);
            LeftDown_RightUp(i, j);
        }
    }
    cout << ans << '\n';

    return 0;
}

구현 후 코드리뷰 + 예제 돌려보기(x)

바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.

디버깅(x)

좋은 코드

대회에서 제시한 솔루션 코드입니다.

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int c=2500000;


int n;
int a[101][101];

int bio[2*c];
int pp[101][101];

int val (int x1,int y1,int x2,int y2)
{
    if ( x1 > 0)
    {
        if (y1 > 0)
        {
            return (pp[x2][y2]+pp[x1-1][y1-1]-pp[x1-1][y2]-pp[x2][y1-1]);
        }
        else
        {
            return (pp[x2][y2]-pp[x1-1][y2]);
        }
    }
    else
    {
        if (y1 > 0)
        {
            return (pp[x2][y2]-pp[x2][y1-1]);
        }
        else
        {
            return pp[x2][y2];
        }
    }
}
int main()
{
    cin>>n;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            cin>>a[i][j];

    pp[0][0]=a[0][0];

    for (int i=1; i<n; i++)
        {
            pp[i][0]=pp[i-1][0]+a[i][0];
            pp[0][i]=pp[0][i-1]+a[0][i];
        }

    for (int i=1; i<n; i++)
        for (int j=1; j<n; j++)
        pp[i][j]=pp[i][j-1]+pp[i-1][j]-pp[i-1][j-1]+a[i][j];

    int rj=0;

    for (int i=1; i<n; i++)
        for (int j=1; j<n; j++)
        {
            for (int x = 0; x < i; x++)
                for (int y=0; y < j; y++)
                    bio[val(x,y,i-1,j-1)+c]++;

            for (int x = i; x < n; x++)
                for (int y=j; y < n; y++)
                        rj+=bio[val(i,j,x,y)+c];

            for (int x = 0; x < i; x++)
                for (int y=0; y < j; y++)
                    bio[val(x,y,i-1,j-1)+c]--;


            for (int x = 0; x < i; x++)
                for (int y=j; y < n; y++)
                    bio[val(x,j,i-1,y)+c]++;

            for (int x = i; x < n; x++)
                for (int y = 0; y < j; y++)
                        rj+=bio[val(i,y,x,j-1)+c];

            for (int x = 0; x < i; x++)
                for (int y=j; y < n; y++)
                    bio[val(x,j,i-1,y)+c]--;


        }
    cout<<rj<<endl;
    //end = clock();
    //cout<< (double)(end - begin) / CLOCKS_PER_SEC<<endl;
    return 0;
}