[코드트리] 기울어진 직사각형 C++

문제

https://www.codetree.ai/missions/2/problems/slanted-rectangle?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

계획 세우기

각 점마다 (가로 1,세로 1) 다이아, (가로 1, 세로 2)다이아 이런 식으로 가능한 범위를 다 찾아보면 될 것 같다

풀이

PointToInspect()에서 (i, j)점에 w, h길이의 직사각형을 검사

 

InspectingRectangles(i, j, w, h)에서 (i, j)에서 오른쪽 위(=우상)로 width만큼 이동, 왼쪽 위(좌상)로 height만큼 이동, 왼쪽 아래(좌하)로 width만큼 이동, 오른쪽 아래(우하)로 height만큼 이동하면서 각 칸의 값을 더해준다.

만약 이동한 칸이 map을 벗어나는 경우 0을 반환한다.

#include <iostream>

using namespace std;

int n, answer;
int map[21][21];

bool InRange(int x, int y){
    return x>=0 && x<n && y>=0 && y<n;
}

// 사각형 검사
int InspectingRectangles(int x, int y, int width, int height){
    // 우상(-1, 1) 좌상(-1, -1) 좌하(1, -1) 우하(1, 1)
    int dx[4] ={-1, -1, 1, 1};
    int dy[4] ={1, -1, -1, 1};

    int sum =0;
    for(int dir=0; dir<4; dir++){
        if(dir%2==0){ // dir방향으로 width만큼 이동
            for(int w=0; w<width; w++){
                x=x+dx[dir];
                y=y+dy[dir];
                if (!InRange(x, y)) return 0;
                sum += map[x][y];
            }
        }
        else{ // dir방향으로 height만큼 이동
            for(int h=0; h<height; h++){
                x=x+dx[dir];
                y=y+dy[dir];
                if (!InRange(x, y)) return 0;
                sum += map[x][y];
            }
        }
    }
    return sum;
}

void PointToInspect(){
    //최소 (2,1) 점은 되어야 1, 2, 3, 4 방향대로 순회할 수 있음
    for(int i=2; i<n; i++){
        for(int j=1; j<n-1; j++){
            // w는 1, 3길이 / h는 2, 4길이
            for(int w=1; w<n-1; w++){
                for(int h=1; h<n-1; h++){
                    answer = max(answer, InspectingRectangles(i, j, w, h));
                }
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }

    PointToInspect();
    cout << answer <<'\n';

    return 0;
}