백준 1937번 - 욕심쟁이 판다

 

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

1937번: 욕심쟁이 판다

 

해당 문제는 다이나믹 프로그램을 사용하는 대표적인 문제이다.

 

일단 문제의 핵심은 아래와 같이 요약할 수 있다.

 

1. 판다는 상,하,좌,우 로 이동이 가능.

2. 지금 자리보다 숫자가 클때만 이동이 가능.

3. 어떤 지역부터 판다를 풀어놔야 최대한 많은 타일을 이동하는지 알고싶음

    (첫번째 타일에 풀어놓는 순간 count는 1이 됨)

 

이해를 위해 아래 그림을 참고하자.

 

아래와 같은 숲이 있을 때 어떤 곳에 판다를 놓으면 최대한 많은 숲을 방문할 수 있을까?

간단한 케이스로 1에서 시작해서 6으로 끝나는게 가장 많은 숲을 방문할 수 있다는 것을 알 수 있다.

 

그럼 어떠한 로직으로 이러한 구성을 만들 수 있을지 생각해보자.

 

아래와 같이 일단 forest 배열과 trace 배열을 각각 만들어준다.

1을 기준으로 오른쪽으로 가던 아래로 가던 조건을 만족하므로 움직이기가 가능하다.

 

아래와 같이 움직였다고 가정해보자.

 

하지만 해당 로직은 콜스택을 쓰기 때문에 마지막 6위치에서

 

다시 상위로 거슬러올라가면서 아래와 같이 계산하게 된다.

 

그림만 봐서는 이해가 안될 수 있으니, 아래의 코드를 참고하자.

 

 

1. JAVA

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class GreedyPandas1937 {
	
	static int N,maxCount;
	static int[][] matrix;
	static int[][] dp;
	static int[] dr = {1,-1,0,0};
	static int[] dc = {0,0,1,-1};
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		matrix = new int[N][N];
		dp = new int[N][N];
		
		
		for (int i = 0; i < N; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				matrix[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		
		for (int i = 0; i < N*N; i++) {
			maxCount = Math.max(maxCount, dynamicPro(i/N, i%N));
		}
		
		bw.write(maxCount + "");
		br.close();
		bw.close();
		
	}
	
	static int dynamicPro(int r, int c) {
		
		if (dp[r][c] != 0 ) return dp[r][c]; 
		dp[r][c] = 1;
		
		for (int i = 0; i < 4; i++) {
			int newR = r + dr[i];
			int newC = c + dc[i];
			
			if (newR >= 0 && newC >= 0 && newR < N && newC < N && matrix[newR][newC] > matrix[r][c]) {
				dp[r][c] = Math.max(dp[r][c],dynamicPro(newR,newC) + 1);
			}
		}
		
		return dp[r][c];
		
	}

}

 

 

2. C++

#include <iostream>
#include <climits>
#include <cstring>

using namespace std;

int N;
int map[501][501];
int dp[501][501];
int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,1,-1};
int max_moving;

int dynamic_prog(int r, int c) {

    if (dp[r][c] != 0) return dp[r][c];
    dp[r][c] = 1;
    
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];

        if (nr >= 0 && nc >= 0 && nr < N && nc < N && map[nr][nc] > map[r][c]) {
            dp[r][c] = max(dp[r][c],dynamic_prog(nr,nc) + 1);
        }
    }

    return dp[r][c];
}


int main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N;

    for (int i = 0; i < N*N; i++) cin >> map[i/N][i%N];

    for (int i = 0; i < N*N; i++) {
        max_moving = max(max_moving,dynamic_prog(i/N,i%N));    
    }    
    
    cout << max_moving;

    return 0;
}