[BaekJoon][1937] 욕심쟁이 판다

BAEKJOON ONLINE JUDGE

1937 욕심쟁이 판다

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

1. Bottom up

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
struct Point {
    int x, y;
    int value;
};
 
bool cmp(const Point &first, const Point &second) {
    return first.value < second.value;
}
 
int n;
Point input[510 * 510];
int map[510][510];
int dp[510][510];
int ans;
 
void print()
{
    int i, j;
 
    printf("\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
}
 
int main()
{
    int i, j;
    int dy[4] = { -1, 0, 0, 1 };
    int dx[4] = { 0, -1, 1, 0 };
    int nexty, nextx;
    Point current;
    int max;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
            input[i * n + j].y = i;
            input[i * n + j].x = j;
            input[i * n + j].value = map[i][j];
        }
    }
 
    sort(input, input + n * n, cmp);
 
    for (i = 0; i < n * n; i++) {
        max = 0;
        current = input[i];
        for (j = 0; j < 4; j++)    {
            nexty = current.y + dy[j];
            nextx = current.x + dx[j];
 
            if (nexty >= 0 && nexty < n && nextx >= 0 && nextx < n) {
                if (map[nexty][nextx] < map[current.y][current.x]) {
                    if (dp[nexty][nextx] > max)    max = dp[nexty][nextx];
                }
            }
        }
 
        dp[current.y][current.x] = max + 1;
 
        if (dp[current.y][current.x] > ans)    ans = dp[current.y][current.x];
    }
 
    printf("%d\n", ans);
 
    return 0;
}

2. Top down

#include <stdio.h>
#include <string.h>
 
int n;
int map[510][510];
int dp[510][510];
int ans;
 
void print()
{
    int i, j;
 
    printf("\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
}
 
void init()
{
    memset(map, -1, sizeof(map));
    memset(dp, -1, sizeof(dp));
}
 
void input()
{
    int i, j;
 
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            scanf("%d", &map[i][j]);
        }
    }
 
}
 
int go(int y, int x)
{
    int i;
    int max = 0;
    int temp;
    int dy[4] = { -1, 0, 0, 1 };
    int dx[4] = { 0, -1, 1, 0 };
 
    if (map[y][x] < 0)    return 0;
    if (dp[y][x] != -1)    return dp[y][x];
    dp[y][x] = 0;
 
    for (i = 0; i < 4; i++) {
        if (map[dy[i] + y][dx[i] + x] < map[y][x]) {
            temp = go(dy[i] + y, dx[i] + x);
            if (temp > max)    max = temp;
        }
    }
    return dp[y][x] = max + 1;
}
 
void solve()
{
    int i, j;
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (dp[i][j] < 0) {
                dp[i][j] = go(i, j);
                if (dp[i][j] > ans)    ans = dp[i][j];
            }
        }
    }
}
 
int main()
{
    init();
 
    input();
 
    solve();
 
    printf("%d\n", ans);
 
    return 0;
}