[BOJ/Gold 5] 백준 27942 :danceplant:(C++)

문제 링크

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

27942번: :danceplant:

문제

춤추는 가지의 모습

흥이 넘치는 우리의 가지는 상하좌우로 몸을 늘이며 춤추는 것을 좋아한다. 춤을 추면 에너지가 소모되기 마련, 가지는 춤을 출 때 에너지를 보충할 수 있도록 주변에 섭취할 양분을 미리 준비해둔다. 가지는 매 순간 최대한의 양분을 섭취하며 열정적으로 춤을 추고 싶어 한다. 자신이 보여줄 수 있는 최고의 춤을 추고 싶어 하는 가지를 위해 어떻게 몸을 늘여야 할지 알려주자.

처음 가지는 N × N(N은 짝수) 격자의 정중앙 2 × 2 공간을 차지하고 있다. 즉 격자의 왼쪽 맨 위 칸의 좌표를 (1, 1), 오른쪽 맨 아래 칸의 좌표를 (N, N)이라고 하면 가지가 차지하는 공간 왼쪽 맨 위 칸의 좌표는 (N2, N2), 오른쪽 맨 아래 칸의 좌표는 (N2 + 1, N2 + 1)이다.

매 순간 가지는 자신이 차지하는 공간의 평행한 두 변의 길이를 상하좌우 중 한 방향으로 1 늘이고, 늘어난 공간에 위치한 양분을 전부 먹는다. 가지는 보여줄 수 있는 최고의 춤을 보여주고 싶기에 현재 가능한 많은 양분을 먹는 방향으로 몸을 늘인다. 만약 그러한 방향이 여럿이면 상하좌우 순으로 우선하여 몸을 늘인다. 만약 몸을 늘일 공간이 없거나 현재 먹을 수 있는 양분이 0 이하라면 더이상 몸을 늘이지 않는다.

입력

첫째 줄에 N이 주어진다. (4 ≤ N ≤ 3,000; N은 짝수)

둘째 줄부터 N개 줄에 격자 위 양분의 정보가 주어진다. 각 양분의 값은 −25이상 25이하의 정수이고, 격자의 중앙 2 × 2는 항상 0이다.

출력

첫째 줄에 가지가 몸을 늘이며 먹은 양분의 총량을 출력한다.

둘째 줄에 가지가 몸을 늘인 방향을 나타내는 문자를 늘인 순서대로 한 줄에 출력한다. 상하좌우는 각각 UDLR에 대응된다.

예제 입력 1

6
3 2 5 -1 9 3
1 0 1 2 3 2
-2 2 0 0 0 1
-4 4 0 0 5 -2
9 2 -2 3 1 2
-8 2 1 -2 1 3

예제 출력 1

49
LRUUDLR

 

알고리즘 분류

• 누적 합

풀이

일일히 상하좌우에 인접해 있는 양분의 총합을 구하려면 시간 초과가 발생하기 때문에 시간을 줄일 방법을 찾아야 한다.

누적 합을 이용해 각 칸까지 도달했을 때의 누적 합을 기록하고, 가지의 상하좌우에 위치한 양분의 총합을 구하고 총합이 가장 높은 방향으로 가지의 크기를 늘려나간다.

예를 들어 좌측에 위치한 양분의 시작점의 (Y좌표, X좌표)가 (2, 3)이고, 끝점이 (5, 3)일 때, (5, 2)까지의 양분의 총합과 (1, 3)까지의 양분의 총합을 (5, 3)까지의 양분의 총합에서 뺀다. 그런데 그러면 (1, 2)까지의 양분의 총합이 중복으로 제외되게 되므로 한 번 더해준다.

이런 식으로 상하좌우에 위치한 양분의 총합을 구하고 양분의 총합이 가장 큰 방향으로 가지의 몸을 늘려나간다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 3001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
pair<int, int> NowFirst, NowLast;
int MAP[MAX][MAX];
int Food;
string Move;

void input() {
    cin >> N;
    NowFirst = make_pair(N / 2, N / 2);
    NowLast = make_pair((N / 2) + 1, (N / 2) + 1);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> M;
            MAP[i][j] = MAP[i - 1][j] + MAP[i][j - 1] - MAP[i - 1][j - 1] + M;
        }
    }
}

void settings() {
    while (1) {
        int NowFood = 0;
        int Dir = -1;
        // 1. 위쪽
        if (NowFirst.first > 1) {
            int Up = MAP[NowFirst.first - 1][NowLast.second] - MAP[NowFirst.first - 2][NowLast.second] - MAP[NowFirst.first - 1][NowFirst.second - 1] + MAP[NowFirst.first - 2][NowFirst.second - 1];
            if (Up > NowFood) {
                NowFood = Up;
                Dir = 0;
            }
        }

        // 2. 아래쪽
        if (NowLast.first < N) {
            int Down = MAP[NowLast.first + 1][NowLast.second] - MAP[NowLast.first][NowLast.second] - MAP[NowLast.first + 1][NowFirst.second - 1] + MAP[NowLast.first][NowFirst.second - 1];
            if (Down > NowFood) {
                NowFood = Down;
                Dir = 1;
            }
        }

        // 3. 왼쪽
        if (NowFirst.second > 1) {
            int Left = MAP[NowLast.first][NowFirst.second - 1] - MAP[NowFirst.first - 1][NowFirst.second - 1] - MAP[NowLast.first][NowFirst.second - 2] + MAP[NowFirst.first - 1][NowFirst.second - 2];
            if (Left > NowFood) {
                NowFood = Left;
                Dir = 2;
            }
        }

        // 4. 오른쪽
        if (NowLast.second < N) {
            int Right = MAP[NowLast.first][NowLast.second + 1] - MAP[NowFirst.first - 1][NowLast.second + 1] - MAP[NowLast.first][NowLast.second] + MAP[NowFirst.first - 1][NowLast.second];
            if (Right > NowFood) {
                NowFood = Right;
                Dir = 3;
            }
        }

        if (NowFood <= 0) {
            break;
        }
        Food += NowFood;
        if (Dir == 0) {
            NowFirst.first--;
            Move += 'U';
        }
        else if (Dir == 1) {
            NowLast.first++;
            Move += 'D';
        }
        else if (Dir == 2) {
            NowFirst.second--;
            Move += 'L';
        }
        else if (Dir == 3) {
            NowLast.second++;
            Move += 'R';
        }
    };
}

void find_Answer() {
    cout << Food << "\n" << Move << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}