C - 1028 다이아몬드 광산

https://www.acmicpc.net/problem/1028

 

다이아(마름모)가 여럿 있을경우 가장 큰 다이아를 구하는 문제이다.

처음 이 문제를 보고 뇌내망상을 몇일동안 여럿 펼쳐보았는데 결과론적으로 아래 그림에서 모순이 발생하지 않는다면 큰

다이아를 구할 수 있다는 결론을 내렸다.

중요한것은 마름모의 한변의 길이를 단박에 구하는것은 불가능해 보인다는 것이다.

 

이 문제는 마름모가 아닌 직사각형으로 먼저 생각하면 초기 아이디어를 잡는데 좀 더 유용했던것같다.

마름모라는 y+1,x-1 / y+1,x+1의 대각을 생각하는것보다 수직의 직각을 생각하는게 좀 더 생각하기에 직관적으로 간단했다.

 

1. 좌하단으로 내려가는 모든 직선을 누적합한다.

2. 우하단으로 내려가는 모든 직선을 누적합한다.

두 누적합을 저장할 별도의 배열을 만들고 누적합의 결과는 그곳에 저장한다.

 

그 후 for문으로 두 배열을 동시에 탐색하며 max edge를 찾는다(한 변의 최대 크기를 찾는문제라서)

마름모의 유효성검사는 해당위치에서 좌상단과 우상단으로 탐색을 하여 해당 위치에 내가 찾으려는 변의 길이 이상의 직선이 있는지 찾으면 된다.

다시 위의 그림을 보면 마름모 한변의 길이를 누적합할 경우 직선의 최대길이만 구할 수 있고 한변의 정확한 길이를 구하는것이 불가능하기 때문이다. 마름모의 유효성을 검사하는것은 이 이상의 최선의 방법은 찾지못했다.

 

누적합코드

void sum_r(int y, int x) {
    if(right[y][x]) return; //이미 누적합 구한 곳은 제외
    right[y][x] = 1;
    while(isSafe(y+1,x+1)) {
        if(board[y+1][x+1])
            right[y+1][x+1] += right[y][x]+1;
        y++; x++;
    }
}

 

마름모의 유효성 검사 코드

void isShape(int y, int x) {
    int edge;
    for(int i=best; i<=right[y][x] && i<=left[y][x]; i++){
        edge=i-1;
        if(right[y-edge][x+edge] >= i && left[y-edge][x-edge] >= i) {
            best = max(i, best);
        }
    }
}

 

전체 코드

https://github.com/shirohebiui/BAEKJOON/blob/0dab65b3ecdd580f7adce0faffed62f487a54404/%23DP/P/1028.c