문제 URL : https://www.acmicpc.net/problem/1890
1890번: 점프
문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거��
www.acmicpc.net
문제 접근법 : 처음 백트래킹으로 메모이제이션 방법으로 풀다 메모리초과되서 백트래킹방법은 맞는데 어디서 잘못된건지 찾질 못하다 백트래킹 방법을 2중 for문으로 찾는방법으로 바꾸었더니 해결했었고
질문 현황해서 백트래킹을 사용할때 메모리 초과 원인을 찾았다
어느 중앙지점에 0 이있을때 이것이 무한 반복을 돌기때문에 스택메모리가 꽉차니 당연했던겁니다.
우선 처음위치에서 출발했을때 그게 처음왔던 출발지점에서 건너온 길이라는걸 표시해주기위해 visit을 사용하였습니다.
그리고 그길로 오기위해 dp를 사용하여 갈수있는 방향들을 다 더해주면 되기 때문에 문제는 상당히 재미있는 문제였습니다.
2가지 소스코드 전부답입니다.
backtracking 방법
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
//by 콩순이냉장고 1890
#include <iostream> #include <string>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n;
int map[100][100];
int visit[100][100];
unsigned long long dp[100][100];
unsigned long long path(int y, int x){
if (y == n - 1 && x == n - 1)
return 1;
if (y >= n || x >= n)
return 0;
if (dp[y][x])//중복 계산을 제거하기위한 메모이제이션 방법
return dp[y][x];
if (visit[y][x])// 계속 멈춰있다면 그것을 피하기위한방법
return 0;
visit[y][x] = 1;
return dp[y][x] = path(y + map[y][x], x) + path(y, x + map[y][x]);//아래 방향 오른쪽방향
}
void input()
{
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> map[i][j];
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
input();
cout << path(0, 0) << "\n";
}
|
cs |
2중 for문 탐색방법 : (확실하진 않지만 이방법이 더빠를거라 생각듭니다.)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
//by 콩순이냉장고 1890
#include <iostream> #include <string>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n;
int map[100][100];
int visit[100][100];
unsigned long long dp[100][100];
void input()
{
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> map[i][j];
}
}
}
bool isrange(int y,int x){
if (0 <= y&&y < n && 0 <= x&&x < n)
return true;
return false;
}
int main(){
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
input();
visit[0][0] = 1;
dp[0][0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int ny = i+map[i][j];
int nx = j;
if (i == n - 1 && j == n - 1)
break;
if (isrange(ny, nx)&&visit[i][j]==1)//현재 내 자리가 출발지점에서 왔다면 아래쪽으로 갈수있는방향
{
dp[ny][nx] += dp[i][j];
visit[ny][nx] = 1;//아래쪽으로 visit 표시
}
ny = i;
nx = j+map[i][j];
if (isrange(ny, nx) && visit[i][j] == 1)//오른쪽으로 갈수있는방향
{
dp[ny][nx] += dp[i][j];
visit[ny][nx] = 1;
}
}
}
cout << dp[n - 1][n - 1] << "\n";
}
|
cs |
궁금한점이나 모르는것이 있다면 어제든지 댓글을 달아주시기 바랍니다 ㅎㅎ
감사합니당.
'백준' 카테고리의 다른 글
| 백준 17835 면접보는 승범이네 (0) | 2020.07.26 |
|---|---|
| 백준 2812 크게만들기 (0) | 2020.07.22 |
| 백준 17830 이진수씨의 하루 일과 (0) | 2020.07.22 |
| 백준 2630 색종이 만들기 (0) | 2020.07.20 |
| 백준 5427 불 (0) | 2020.07.20 |
