https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
풀이는 쉽게 해결했는데 시간초과 발생했습니다. 생각보다 어렵다 판단하였고 아직 dp익숙치 않아서 질문게시판을 봤습니다
어렵네요.. 어느정도 아이디어를 얻긴했는데 도저히 시간초과를 해결할수 없었습니다. 힌트덕분에 해결은 했습니다.
여기서 키 포인트는 겹치는 부분에서 거꾸로 돌아간다입니다.
즉 만나는 지점에서 거꾸로 돌아가면서 누적값을 합치는건데 dp를 어떻게 설정해주냐가 포인트입니다.
먼저 dp를 전부 -1로 초기화 하고 dp가 -1이 아닐때 return을 시킵니다. 즉 처음에는 무조건 지나갈수 있게하고 그 다음부터는 돌아가게하는게 포인트입니다. 이때 누적값을 합하면서 돌아가야합니다.
#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
#include<stack>
using namespace std;
struct Point {
int i, j;
int size ;
int cnt=0;
int eat = 0;
};
void Prints(vector<vector<int>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<char>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<char>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<bool>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
void Prints(vector<int>line, int n) {
for (int i = 0; i < n; i++) {
cout << line[i] << ",";
}
cout << endl;
}
void Prints(string str, int n) {
for (int i = 0; i < n; i++) {
cout << str[i] << ",";
}
cout << endl;
}
bool checkmaps(vector<vector<int>>maps, vector<vector<int>>anw, int n, int m) {
bool bCheck = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maps[i][j] != anw[i][j]) {
bCheck = true;
i = n + 1;
j = m + 1;
continue;
}
}
}
return bCheck;
}
bool findstart(vector<vector<int>>maps, vector<vector<int>>anw, int n, int m, int) {
bool bCheck = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maps[i][j] != anw[i][j]) {
bCheck = true;
i = n + 1;
j = m + 1;
continue;
}
}
}
return bCheck;
}
struct Data {
Point p;
int cnt;
int sum;
};
bool cmp(const Point &a, const Point &b) {
if (a.cnt == b.cnt) {
if (a.i == b.i) {
//왼쪽
return a.j < b.j;
}
//위쪽
return a.i < b.i;
}
//거리 짧은
return a.cnt < b.cnt;
}
int n, m;
vector<vector<int>>maps;
vector<vector<bool>>gbVisited;
vector <vector<int>>dp;
int diri[] = { 1,-1,0,0 };
int dirj[] = { 0,0,1,-1 };
int gcnt = 0;
int backtraking(Point p) {
if (p.i == n - 1 && p.j == m - 1) {
return 1;
}
if (dp[p.i][p.j] !=-1) {
return dp[p.i][p.j];
}
dp[p.i][p.j] = 0;
for (int i = 0; i < 4; i++) {
int tmpDiri = diri[i] + p.i;
int tmpDirj = dirj[i] + p.j;
if (tmpDiri == -1 || tmpDirj == -1 || tmpDiri >= n || tmpDirj >= m) {
continue;
}
if (gbVisited[tmpDiri][tmpDirj] == true) {
continue;
}
if (maps[p.i][p.j] > maps[tmpDiri][tmpDirj]) {
Point tmpP;
tmpP.i = tmpDiri;
tmpP.j = tmpDirj;
dp[p.i][p.j]+= backtraking(tmpP);
}
}
return dp[p.i][p.j];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
vector<bool>tmpbVisted(m,false);
vector<vector<bool>>bVisted(n, tmpbVisted);
vector<int>tmpdp(m, -1);
vector<vector<int>>tmpdpd(n, tmpdp);
dp = tmpdpd;
gbVisited = bVisted;
for (int i = 0; i < n; i++) {
vector<int>tmpMaps;
for (int j = 0; j < m; j++) {
int tmp;
cin >> tmp;
tmpMaps.push_back(tmp);
}
maps.push_back(tmpMaps);
}
Point p;
p.i = 0;
p.j = 0;
int ans=backtraking(p);
cout << ans;
}