[14430번] 자원 캐기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

이 문제를 처음에는 DFS로 접근하였으나 시간 초과를 받게 되었다.

즉, 가로 세로가 300이하이고 이동 방향이 오른쪽, 아래 방향뿐이니 break문을 적절히 섞으면 성공할 것이라 생각했는데 

이 문제를 DFS로 풀게 되니 시간 초과를 받게 되었다.

결국 DP를 통해 문제를 해결하게 되었다.

점화식은 다음과 같다.

map[i][j] :: 처음 입력 받는 map이자 정답을 도출하는 배열

map[i][j] += max(map[i - 1][j], map[i][j - 1]);

즉, map의 현재 위치에서 왼쪽 혹은 위쪽의 map 값 중 더 큰 값을 계속 가져오는 방식을 이용한다.

소스 코드는 배열을 이용하는 방식과 벡터를 이용하는 방식 두가지를 구현하였다.

벡터를 이용하여 동적으로 만들면 메모리 사용량이 줄 것이라 생각했으나.

배열을 302로 고정하고 푸는 것이 메모리 사용은 조금 더 적었다.

소스 코드 : 

< 배열 크기를 고정한 코드 >

#include <iostream>
#include <cstdio>
#include <algorithm>
 
#define MAXSIZE 302
 
using namespace std;
 
int map[MAXSIZE][MAXSIZE];
 
int main()
{
    int n, m;
    int maxVal = 0;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &map[i][j]);
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            map[i][j] += max(map[i - 1][j], map[i][j - 1]);
 
            if (map[i][j] > maxVal)
                maxVal = map[i][j];
        }
    }
 
    printf("%d", maxVal);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

< 벡터를 이용한 코드 >

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
vector<vector<int>> vc;
 
int main()
{
    int n, m;
    int val = 0;
    int maxVal = 0;
    
    scanf("%d %d", &n, &m);
 
    vc.push_back(vector<int>(302, 0));
 
    for (int i = 0; i < n; i++)
    {
        vector<int> tvc;
        tvc.push_back(0);
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &val);
            tvc.push_back(val);
        }
        vc.push_back(tvc);
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            vc[i][j] += max(vc[i - 1][j], vc[i][j - 1]);
 
            if (vc[i][j] > maxVal)
                maxVal = vc[i][j];
        }
    }
 
    printf("%d", maxVal);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>