[Baekjoon] 욕심쟁이 판다(BOJ 1937)

👀 문제 설명

문제

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

 

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

 

예제 입력 1

4

14 9 12 10

1 11 5 4

7 15 2 13

6 3 16 8

 

예제 출력 1

4

✍🏻풀이

처음에는 입력받은 대나무의 양 중 가장 작은 것부터 순서대로 Dynamic Programming을 하면 된다고 생각해서, 제일 작은 값과 위치를 저장해뒀다.

이렇게 하니까 너무 복잡해지고 그 다음 작은 값은 또 어떻게 구해야할지 막막해졌다 :(

 

그래서 구글링을 통해.. 알아낸 방법은 다음과 같다.

 

상수 선언

#define MAX 500 : 대나무 숲의 크기는 최대 500

 

필요한 변수

int n : 입력받을 대나무 숲의 크기

int forest[MAX][MAX] : 대나무 숲의 각각 위치에 대나무 양이 얼마나 있는지를 입력받을 테이블

int dx[4] & int dy[4] : 상, 하, 좌, 우를 위한 배열

int dp[MAX][MAX] : Dynamic Programming을 위한 테이블

 

알고리즘

1. 대나무 숲을 입력받는다.

2. 각각의 위치에서 Dynamic Programming을 다 해본다.

    -> 이 때, 메모이제이션(Memoization) 사용! (참고 : [Algorithm] Dynamic Programming)

3. 그 중 제일 큰 값이 답 (max 함수 사용)

쓰니까 너무 간단하네..

 

코드

//
//  BOJ_1937.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/05/17.
//  Copyright © 2020 조수민. All rights reserved.
//
//  욕심쟁이 판다(https://www.acmicpc.net/problem/1937)

#include <iostream>
#include <vector>
#define MAX 500 // 대나무 숲 크기는 최대 500
//#define BAMBOO 1000000 // 대나무 양은 최대 1,000,000 (이지만, 사용하지 않는 값)

using namespace std;

int n; // 대나무 숲 크기
int forest[MAX][MAX];
int dx[4] = { -1, 1, 0, 0 }; // 상, 하, 좌, 우
int dy[4] = { 0, 0, -1, 1}; // 상, 하, 좌, 우
int dp[MAX][MAX]; // dp 저장공간..

// 대나무 숲 입력받기
void input()
{
    cin >> n;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            dp[i][j] = 1; // dp를 1로 초기화해둔다.
            cin >> forest[i][j];
        }
}

int get_day(int x, int y)
{
    int &day = dp[x][y];
    
    if (day != 1)
        return day;
    
    for (int i = 0; i < 4; i++)
    {
        int next_x = x + dx[i];
        int next_y = y + dy[i];
        
        // next_x와 next_y가 범위를 벗어난다면 continue문 수행
        if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= n)
            continue;
        
        // 다음 위치의 대나무 양이 현재 위치의 대나무 양보다 클 떄만 다음을 수행한다.
        if (forest[next_x][next_y] > forest[x][y])
        {
            // 메모이제이션 사용!
            int next_dynamic = get_day(next_x, next_y) + 1; // 다음으로 이동해서 그 자리에서 또 get_day를 한다.
            day = max(day, next_dynamic); // day와 next_dynamic 중 더 큰 값을 day에 넣어준다.
        }
    }
    
    return day;
}

int get_answer()
{
    int answer = 0;
    
    // 각각의 위치에서 dynamic_programming을 다 해본다.
    // 그 중 제일 큰 값이 답
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            answer = max(answer, get_day(i, j)); // 매번 answer와 (i, j) 위치에서의 dynamic_programming 값을 비교하여 더 큰 값을 answer로 바꿔준다.
    
    return answer;
}

int main()
{
    input();
    
    cout << get_answer() << endl;
    
    return 0;
}