더블릿_어망투망

다차원 배열을 다루는 부분이 쉬운 줄 알았는데 의외로 조금 시간이 걸렸다.

더군다나 마지막에 엄청난 오류를 범해서 틀린 것이 있었다. 

이 문제는 다차원배열을 이해하고 활용하는데 아주 좋은 문제이기 때문에 몇 번이고 다시 풀어볼 필요가 있을 것 같다.

문제정리)

5 * 5배열에서 어망을 투하해서 가장 많은 수확을 할 수 있는 범위와 그 값을 구하는 문제였다. 

문제풀이)

우선 5*5배열이기 때문에 어림잡아 5 * 5 * 5 * 5 * 5 * 5 이하의 순회를 하게 되는데 , 

15625번? 물론 이 것보다 훨씬 적게 반복문을 수행하는데, 어쨋든 1억번까지 수행하지 않으므로 1초안에 무조건 해결 가능하다. 그렇기 때문에 완전탐색으로 풀면 된다. 

배열의 인덱스 x, y에 접근하게 되면 그 점을 기준으로 오른쪽으로 아래쪽으로 사각형을 모두 만들어보면서 답을 구했다. 

void calc(int x, int y){
    for (int i = 1; i <= 6 - x; i++){
        for (int j = 1; j <= 6 - y; j++){
            // if (i == j) continue;
            int sum = 0;
            for (int a = x; a <= x - 1 + i; a++){
                for (int b = y; b <= y - 1 + j; b++){
                    sum += arr[a][b];
                }
            }
            if (sum > maxvalue) { 
                maxvalue = sum; 
                start_x = x; start_y = y;
                end_x = x - 1 + i; end_y = y - 1 + j;
            }
        }
    }
}
 

1번째 for문과 2번째 for문으로 사각형의 범위를 잡고

3번째 for문과 4번째 for문으로 영역에 속하는 합을 구했다. 

사각형의 범위는 

세로는 1부터 ~ 6 - 현재점x   까지의 범위를 

가로는 1부터 ~ 6 - 현재점y   까지의 범위를 잡았다.

그 안에 속한 사각형의 어획량을 계산하는 부분에서는

현재점부터 어획량의 범위까지의 길이까지를 반복문을 통해 잡아주었다. 

이 것은 말로 설명하기보다 몇 번이고 다시 풀어보면서 머리속으로 정리해주어야 하는 것 같다.

또 하나 나를 애먹인건 

정사각형과 직사각형의 차이였다.

중고등학교 때 잘못된 지식을 가지고 있어서 애를 먹었다. 

-직사각형은 4각이 90도이고 마주보는 한쌍의 길이가 같은 사각형이다. 

-정사각형은 4각이 90도이고 마주보는 두쌍의 길이가 모두 같은 사각형이다.

직사각형은 무조건 마주보는 한쌍의 길이만 같아야 되는 줄 알았다. 

인터넷을 찾아보니 직사각형은 정사각형에 포함되는 사각형이란다.