영지 선택 Territory large

문제

세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다. 전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨져 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 다음과 같은 땅의 정보가 주어지고, 현수가 하사받을 크기가, 가로 2, 세로 3의 크기이면 가장 많은 오렌지 나무가 있는 영지는 총 오렌지 나무의 개수가 16인 3행 4열부터 시작하는 구역이다.

 

고찰

처음 시도했던 방식은 간단히 설명하면 다음과 같다.

구현하고 보니 아주 잘못된 방식이었기 때문에 자세히 설명하지는 않겠다.

예시 데이터를 수동으로 계산했을 때 최대값도 정확하게 잘 나오는 듯 보였다.

하지만 막상 구현해보니....

노란 사각형 부분을 계산하는 것이 곧 2중 for문이라는 것을 생각하지 못하고 맞은 최후

for문의 변수명을 i, j, k까지 쓰고 나서야 이 코드가 4중 for문이 될 것임을 알았다.

완성된 코드를 돌려보니 값은 정확하지만, 현수의 영토 크기가 커지자 값을 구하는 속도가 급격하게 느려졌다.

생각해보면 그냥 맨 앞부터 끝까지 4중 for문을 돌리며 최대값을 갱신해 주는 것과 결국 똑같다.

그래도 이전 영역의 최대값을 이용해 다음 영역의 최대값을 구하려고 시도했다는 점에 의의를 두고 싶다.......

 

해결

처음 영 정보를 받아올 때, 해당 인덱스를 우하단 꼭지점으로 가지는 범위의 오렌지 나무 총 갯수를 다른 2중 배열에 저장한다.

vecTerri[0][0] 일 때 누적값은 (값이 한 개밖에 없으므로) 당연하게도 3이다.

 

 

vecTerri[0][1] 일 때 누적값(빨간 사각형 범위의 오렌지 나무 총합)은 기존의 3과 새로 만난 5 값을 더하여 8이다.

단순히 3 + 5 = 8이 아니라 기존 누적값 3에 새로 들어간 값 5을 더해서 8을 얻었다고 생각해야 한다.

 

 

따라서 첫 번째 줄의 누적값은 다음과 같이 18이라는 것을 구할 수 있다.

vecTerri[1][0] 일 때 누적값은 다시 vecTerri[0][0]의 값을 가지고 계산해야 한다.

vecTerri[1][0] 를 우하단 꼭지점으로 가지는 사각형에 vecTerri[0][1],  vecTerri[0][2]...  는 포함되지 않기 때문이다.

따라서 누적값은 기존의 3에 새로 들어간 값 1을 더해서 4가 된다.

이제 vecTerri[1][1] 일 때의 누적값을 구해야 한다. 이제는 단순히 이전 값 + 새로 만난 값 계산으로는 구할 수 없다.

구해야 하는 범위(빨간 사각형)에서 새로운 값(초록 사각형)을 뺀 부분의 모양이 사각형이 아니라 ㄱ자 모양이기 때문이다.

하지만 여기서 이제까지 저장해온 누적값을 통해 저 ㄱ자 모양 영토를 분해해서 생각할 수 있다.

앞서 우리는 보라색 사각형 범위의 누적값 4와 파란색 사각형 범위의 누적값 8을 누적값 표에 기록하고 있었기 문이다.

즉 아래 그림에서 빨간 영역의 범위는 보라색 사각형 + 파란색 사각형 값에, 두 사각형을 더하는 과정에서 중복되게 더해진 노란색 사각형 값을 빼준 것과 같다는 것을 알 수 있다.

따라서 vecTerri[1][1] 일 때의 누적값은 4 + 8 - 3 에 새로 들어간 2를 더해서 11이 된다.

이 방식으로 모든 칸의 누적값을 계산할 수 있다.

예를 들어 vecTerri[2][4]까지의 누적값은 보라색 사각형 + 파란색 사각형 - 노란색 사각형 + 초록색 사각형 = 29 + 21 - 19 + 1 = 32로 계산할 수 있다.

하지만 이 규칙을 사용하자니 영토의 맨 윗줄과 맨 왼쪽 줄, 즉 vecTerri[0][n]일 때와 vecTerri[n][0]일 때가 걸린다.

이 경우 초록색 사각형이 가장자리에 붙어 위나 왼쪽에 존재하는 보라색, 파란색, 노란색 사각형이 존재하지 않을 수 있기 때문이다.

이 문제를 해결하기 위해 누적 값을 저장하고 있는 2중 배열에 윗줄과 왼쪽 줄을 하나 더 추가하고, 이것을 0으로 채우는 방법을 사용할 수 있다. (물론 이 경우 보라색, 파란색, 노란색 사각형이 전부 0이기 때문에 값 자체에 영향을 끼치진 않는다)

따라서 이제 영토 vecTerri에 대해 다음과 같은 공식을 사용할 수 있다.

새 칸의 누적값 = 보라색 사각형 + 파란색 사각형 - 노란색 사각형 + 초록색 사각형(새 칸의 값)

→ i, j > 0일 때, vecSum[i][j] = vecSum[i][j-1] + vecSum[i-1][j] - vecSum[i-1][j-1] + vecTerri[i-1][j-1] 

위 공식을 이용해서 vecSum을 완성해준다.

심지어 스프레드 시트에서도 위 공식을 사용했더니 아주 쉽게 vecSum표를 완성할 수 있었다

이제 vecTerri[n][m]을 우하단 꼭지점으로 가지는 현수 땅의 오렌지 나무 수를 구해 최대값을 계산하면 된다.

vecSum을 이용하면 고찰에서처럼 2중 for문을 돌지 않고도 특정 땅의 오렌지 나무 수를 구할 수 있다.

아래 그림에서 초록색으로 색칠된 영토의 오렌지 나무 수를 구하고자 한다면, 빨간색 사각형 - 보라색 사각형 - 파란색 사각형 + 노란색 사각형을 해주면 되고, 이 값들은 모두 vecSum에 인덱스 접근이 가능한 형태로 저장되어있다.

즉 vecTerri[3][5] 칸을 우하단 꼭지점으로 하는 현수 땅의 오렌지 나무 수 = vecSum[4][6] - vecSum[4][3] - vecSum[2][6] + vecSum[2][3] = 53 - 25 -25 +13 = 16 이라는 것을 알 수 있다.

이를 공식으로 표현하면 다음과 같다.

현수의 땅이 세로 크기 n, 가로 크기 m일 때, vecTerri[i][j]를 우하단 꼭지점으로 하는 현수 땅의 오렌지 나무 수는

vecSum[i+1][j+1] - vecSum[i+1][j+1-m] - vecSum[i+1-n][j+1] + vecSum[i+1-n][j+1-m] 이다.

이때 i는 n-1부터, j는 m-1부터 시작해야 한다. (그것보다 작으면 현수 땅의 크기가 다 들어가지 못하므로)

 

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int nTerriH, nTerriW; //세종대왕 영역 세로, 가로 크기 지정
    cin >> nTerriH >> nTerriW;

    vector<vector<int>> vecTerri(nTerriH, vector<int>(nTerriW)); //세종대왕 영역 2중 벡터
    vector<vector<int>> vecSum(nTerriH + 1, vector<int>(nTerriW + 1)); //누적값 저장할 2중 벡터

    for (int i = 1; i <= nTerriH; ++i)
    {
        for (int j = 1; j <= nTerriW; ++j)
        {
            //세종대왕 땅에 1~9개의 오렌지 나무를 랜덤으로 심는다
            int nOrange = rand() % 9 + 1;
            vecTerri[i-1][j-1] = nOrange;

            //vecSum에 해당 인덱스 영역을 우하단 꼭지점으로 갖는 땅의 오렌지 나무 합계를 저장한다
            vecSum[i][j] = vecSum[i][j - 1] + vecSum[i - 1][j] - vecSum[i - 1][j - 1] + vecTerri[i - 1][j - 1];

            cout << nOrange << " ";
        }
        cout << endl;
    }

    int nMyH, nMyW; //현수 땅의 세로, 가로 크기 지정
    cin >> nMyH >> nMyW;

    int nMaxOrange = 0; //현수 땅이 가질 수 있는 최대 오렌지 나무 수 저장할 변수

    for (int i = nMyH - 1; i < nTerriH; ++i)
    {
        for (int j = nMyW - 1; j < nTerriW; ++j)
        {
            //vecSum을 이용해서 vecTerri[i][j]를 우하단 꼭지점으로 갖는 현수 땅의 오렌지 나무 수를 계산
            int nTempOrange = vecSum[i + 1][j + 1] - vecSum[i + 1][j + 1 - nMyW] - vecSum[i + 1 - nMyH][j + 1] + vecSum[i + 1 - nMyH][j + 1 - nMyW];
            //그 값이 기존에 저장되어 있던 값보다 크면 갱신
            if (nTempOrange > nMaxOrange)
                nMaxOrange = nTempOrange;
        }
    }

    cout << nMaxOrange << endl;

    return 0;
}

 

테스트

같은 rand()값을 가지고 4중 for문 방식과 정답 방식(다이나믹 프로그래밍)을 돌려보았다. (땅 크기 700x700, 현수 땅 100x100)

clock_t 를 이용해 현수 땅의 세로, 가로 값을 입력받은 후부터 정답 출력까지 걸린 시간을 표시했다.

4중 for문 방식은 어떤 컴퓨터에서 돌리느냐에 따라 차이가 엄청나게 난다. (같은 코드여도 다른 컴퓨터에서는 70초대가 나왔다.)

반면 다이나믹 프로그래밍 방식은 어떤 컴퓨터에서든 0.1초 아래를 유지했다.

4중 for문 방식(고찰)은 좋은 컴퓨터에서 돌려도 20초나 걸린다.

다이나믹 프로그래밍 방식(해결). 컴퓨터 성능에 관계 없이 늘 저 정도로 나온다.

밭 값을 랜덤으로 하지 않고 예시와 똑같이 넣어주었을 때도 답 16이 잘 나온다.